Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdafx.h"
- #include <stdint.h>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- vector<int64_t> factorialValues(1,1);
- int64_t factorial(int n);
- int64_t countPermutations(int numStats, int maxSum, int maxIndividual);
- int64_t countPermutations(int numStats, int spotsLeft, int maxSum, int sumLeft, int smallestNum, vector<int> nums);
- int main()
- {
- cout << "PERMUTATIONS OF EV STATS: " << countPermutations(6, 510, 252);
- //cin to prevent window from closing before we can see the result
- char x;
- cin >> x;
- return 0;
- }
- //Non-recursive version
- int64_t countPermutations(int numStats, int maxSum, int maxIndividual)
- {
- vector<int> nums(numStats, -1);
- return countPermutations(numStats, numStats, maxSum, maxSum, maxIndividual, nums);
- }
- int64_t countPermutations(int numStats, int spotsLeft, int maxSum, int sumLeft, int smallestNum, vector<int> nums)
- {
- //Prune out possibilities that don't work
- if (smallestNum * spotsLeft < sumLeft || sumLeft < 0)
- return 0;
- //Base case for recursion
- if (spotsLeft == 0)
- {
- //Figure out how many permutations of this given nums vector there are.
- vector<int> Numbers, howManyRepeat;
- int64_t num = factorial(numStats);
- for (int i = 0; i < numStats; i++)
- {
- int value = nums[i];
- int index = find(Numbers.begin(), Numbers.end(), value) - Numbers.begin();
- //If found, increment howManyRepeat
- if (index < Numbers.size())
- howManyRepeat[index]++;
- else
- {
- //If not, add it in
- Numbers.push_back(value);
- howManyRepeat.push_back(1);
- }
- }
- for (int i = 0; i < howManyRepeat.size(); i++)
- num /= factorial(howManyRepeat[i]);
- return num;
- }
- //Create variable to store whole sum and which numbers to check, derived from smallestNum * spotsLeft >= sumLeft
- int64_t sum = 0;
- int minimum = sumLeft / spotsLeft;
- for (int a = min(smallestNum, sumLeft); a >= minimum; a--)
- {
- int64_t tmp = sum;
- vector<int> newNums(nums);
- newNums[numStats - spotsLeft] = a;
- sum += countPermutations(numStats, spotsLeft - 1, maxSum, sumLeft - a, a, newNums);
- if(numStats == spotsLeft)
- cout << a << " " << (sum - tmp) << endl;
- }
- return sum;
- }
- int64_t factorial(int n)
- {
- //Use a lookup table for performance, we're going to be calling this a lot!
- if (n < (int)factorialValues.size())
- return factorialValues[n];
- for (int i = factorialValues.size(); i <= n; i++)
- factorialValues.push_back(i * factorialValues[i - 1]);
- return factorialValues[n];
- }
Advertisement
Add Comment
Please, Sign In to add comment