   Permutations and combinations
  I've been working on a fairly complex algorithm, but ran into a part that i'm having trouble finding a solution for every situation in a reasonable time.Let me start with a smaller version of the problem.Say I have a value of 12 and up to a 4 digit number.  I need to find all the combinations of digits that sum up to the value.  The numbers i'm working with are much larger like 10^20 but this serves the purpose.I started with a top down approach to filling the number ( more greedy ).My idea is it would go like this for the value 129300, 9210, 91118400, 8310, 8220, 82117500, 7410, 7320, 7311, 72216600, 6510, 6420, 6411, 6330, 6321, 62225520, 5511I'm not worried about the differences in numbers 3900, 9300, just that that somewhere in the number are digits 3 and 9.The only problem is my algorithm is basically O( n * n * n * n ) where n is the number of digits.In pseudo code the simpliest solution isa = 9 -> 5  b = 9 -> 0    c = 9 -> 0 d = 9 -> 0   if( a + b + c + d == 12 && NotAlreadyFound )//Found OneSo in this brute force method is pretty much 9^n where is the number of digits.There are some ways to improve this method, but it doesn't get it to the O(n) or maybe even O(n^2) time I need.Does anyone have suggestions on how to approach this.ThanksAdam[Edited by - adam23 on May 29, 2010 10:50:47 AM]
Quote:Say I have a value of 12 and up to a 4 digit numberLet 12 be m, and let 4 be n.What are the maximum values for m and n?Quote:find all the combinations Find? Or just count how many there are?If it's find, then the algorithm will inevitably be around n^m, since all possible results need to be printed.   ;Quote:Original post by AntheusQuote:Say I have a value of 12 and up to a 4 digit numberLet 12 be m, and let 4 be n.What are the maximum values for m and n?Quote:find all the combinations Find? Or just count how many there are?If it's find, then the algorithm will inevitably be around n^m, since all possible results need to be printed.The maximum value for m would 180 ( 9 * 20 digits ).The maximum value for n would 20 in my algorithm.The count part is fairly complex so i'll do my best to explain.In the example above lets take 9111.I need to first find 9111 and then count the number of combinations it could possibly have.  So in this example it would be 4!/3! since there are only 2 unique numbers one with 3 and the other with one digit.So really the second part of my algorithm is very simple, sort, and calculate the number of permutations.  Its finding all the numbers to calculate the permutations that I was afraid was going to be exponential time.Maybe theres another way to approach this.I've tried these.-I started with a 0 - 9^20 approach that just calculates the sum and compares to something else to see if its correct.  This didn't even get 1% done in one day.-So then I thought maybe working in reverse with taking the max sum and working down, finding all the possible numbers etc.  This isn't seeming possible.ThanksAdam;  Let q be a number whoe digits sum to m.Then Q without digit i sums to m-Q. 9300 = 12 and 300 = 12-9 and 900 = 12-3.Since this can be applied recursively, we need terminating condition. In this case, Q is a sum precisely when there is a single digit left, equal to sum, or when there are no digits left, and sum in zero.It's easy to see above 300 = 3, 30 = 3, 3 = 3, 0 = 0, or 300 = 3, 00 = 0, 0 = 0.Writing this recursively:int count(int sum, int len) {  if (sum < 0) return 0; // invalid  if (len == 0) return (sum == 0) ? 1 : 0; // maybe we found a valid permutation  // we have at least one digit left, so try all possibilities  int total = 0;  for (int i = 0; i < 10; i++) total += count(sum-i, len-1);  return total;}And voila.Of course, there is still that tedious 10^n problem...Enter memoization:const int N = 200;const int M = 9*N+1;int memo[M][N];int count(int sum, int len) {if (sum < 0) return 0;if (len == 0) return (sum == 0) ? 1 : 0;int  total = memo[sum][len];if (total == -1) {total = 0;for (int i = 0; i < 10; i++) total += count(sum-i, len-1);memo[sum][len] = total;    }return total;}void reset() {for (int i = 0; i < M; i++)for (int j = 0; j < N; j++) memo[j] = -1;}int main(){reset();std::cout << count(1423, 196) << std::endl;}Obviously, int, either 32 or 64 bit is far from enough for most n. This type of assignments usually asks for result via modulo X to avoid overflow issues. If overflow occurs in above version, the intermediate result can be -1, which is same as sentinel, so the result can be incorrect. Using something like:total = (total + count(sum-i, len-1)) % 12345;can help if all that's needed is modulo.The above is straight-forward application of memoization to recursion. Non-recursive implementations are possible as well, avoiding stack size issues when n is in thousands.[Edited by - Antheus on May 29, 2010 3:54:04 PM];  I still can't figure out what the problem really is. The OP didn't say that he needed to "count" anything: He said he needed to "find" certain combinations. To me that means that he needs a list, not just a count.Can you please clarify exactly what you want?   