Ipquarx

Generalized Partition Calculator

Apr 8th, 2016
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #include "stdafx.h"
  2. #include <stdint.h>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. vector<int64_t> factorialValues(1,1);
  10.  
  11. int64_t factorial(int n);
  12. int64_t countPermutations(int numStats, int maxSum, int maxIndividual);
  13. int64_t countPermutations(int numStats, int spotsLeft, int maxSum, int sumLeft, int smallestNum, vector<int> nums);
  14.  
  15. int main()
  16. {
  17.     cout << "PERMUTATIONS OF EV STATS: " << countPermutations(6, 510, 252);
  18.  
  19.     //cin to prevent window from closing before we can see the result
  20.     char x;
  21.     cin >> x;
  22.  
  23.     return 0;
  24. }
  25.  
  26. //Non-recursive version
  27. int64_t countPermutations(int numStats, int maxSum, int maxIndividual)
  28. {
  29.     vector<int> nums(numStats, -1);
  30.     return countPermutations(numStats, numStats, maxSum, maxSum, maxIndividual, nums);
  31. }
  32.  
  33. int64_t countPermutations(int numStats, int spotsLeft, int maxSum, int sumLeft, int smallestNum, vector<int> nums)
  34. {
  35.     //Prune out possibilities that don't work
  36.     if (smallestNum * spotsLeft < sumLeft || sumLeft < 0)
  37.         return 0;
  38.  
  39.     //Base case for recursion
  40.     if (spotsLeft == 0)
  41.     {
  42.         //Figure out how many permutations of this given nums vector there are.
  43.         vector<int> Numbers, howManyRepeat;
  44.         int64_t num = factorial(numStats);
  45.  
  46.         for (int i = 0; i < numStats; i++)
  47.         {
  48.             int value = nums[i];
  49.  
  50.             int index = find(Numbers.begin(), Numbers.end(), value) - Numbers.begin();
  51.  
  52.             //If found, increment howManyRepeat
  53.             if (index < Numbers.size())
  54.                 howManyRepeat[index]++;
  55.             else
  56.             {
  57.                 //If not, add it in
  58.                 Numbers.push_back(value);
  59.                 howManyRepeat.push_back(1);
  60.             }
  61.         }
  62.  
  63.         for (int i = 0; i < howManyRepeat.size(); i++)
  64.             num /= factorial(howManyRepeat[i]);
  65.  
  66.         return num;
  67.     }
  68.  
  69.     //Create variable to store whole sum and which numbers to check, derived from smallestNum * spotsLeft >= sumLeft
  70.     int64_t sum = 0;
  71.     int minimum = sumLeft / spotsLeft;
  72.  
  73.     for (int a = min(smallestNum, sumLeft); a >= minimum; a--)
  74.     {
  75.         int64_t tmp = sum;
  76.         vector<int> newNums(nums);
  77.         newNums[numStats - spotsLeft] = a;
  78.  
  79.         sum += countPermutations(numStats, spotsLeft - 1, maxSum, sumLeft - a, a, newNums);
  80.  
  81.         if(numStats == spotsLeft)
  82.             cout << a << " " << (sum - tmp) << endl;
  83.     }
  84.  
  85.     return sum;
  86. }
  87.  
  88. int64_t factorial(int n)
  89. {
  90.     //Use a lookup table for performance, we're going to be calling this a lot!
  91.     if (n < (int)factorialValues.size())
  92.         return factorialValues[n];
  93.  
  94.     for (int i = factorialValues.size(); i <= n; i++)
  95.         factorialValues.push_back(i * factorialValues[i - 1]);
  96.  
  97.     return factorialValues[n];
  98. }
Advertisement
Add Comment
Please, Sign In to add comment