Number of possible combinations

Question

How many possible combinations of variables a, b, c, d, e are possible if I know that:

a+b+c+d+e = 500 

and that they are all integers and> = 0, so I know that they are finite.

Answer 1

@Torlack, @Jason Cohen: Recursion is a bad idea here because there are "overlapping subtasks". Ie If you select a as 1 and b as 2 , then you will have 3 variables left, which must contain up to 497; you come to the same subtask, choosing a as 2 and b as 1 . (The number of such matches explodes as the numbers grow.)

The traditional way to attack such a problem is through dynamic programming : build a table of bottom-up solutions for sub-problems (starting with “how many combinations of 1 variable add up to 0?”), And then build through iteration (solution “how many combinations of n variables add up up to k? "is the sum of the solutions" how many n-1 combinations are added to j? "with 0 <= j <= k).

 public static long getCombos( int n, int sum ) { // tab[i][j] is how many combinations of (i+1) vars add up to j long[][] tab = new long[n][sum+1]; // # of combos of 1 var for any sum is 1 for( int j=0; j < tab[0].length; ++j ) { tab[0][j] = 1; } for( int i=1; i < tab.length; ++i ) { for( int j=0; j < tab[i].length; ++j ) { // # combos of (i+1) vars adding up to j is the sum of the # // of combos of i vars adding up to k, for all 0 <= k <= j // (choosing i vars forces the choice of the (i+1)st). tab[i][j] = 0; for( int k=0; k <= j; ++k ) { tab[i][j] += tab[i-1][k]; } } } return tab[n-1][sum]; } 

  $ time java Combos
 2656615626

 real 0m0.151s
 user 0m0.120s
 sys 0m0.012s

Answer 2

The answer to your question: 2656615626 .

Here is the code that generates the response:

 public static long getNumCombinations( int summands, int sum ) { if ( summands <= 1 ) return 1; long combos = 0; for ( int a = 0 ; a <= sum ; a++ ) combos += getNumCombinations( summands-1, sum-a ); return combos; } 

In your case, summands is 5 and sum is 500.

Please note that this code is slow . If you need speed, cache the results from summand,sum pairs.

I assume you need the numbers >=0 . If you want >0 , replace the loop initialization with a = 1 and the loop condition with a < sum . I also assume that you want permutations (e.g. 1+2+3+4+5 plus 2+1+3+4+5 , etc.). You can change the for loop if you want a >= b >= c >= d >= e .

Answer 3

In fact, this would be a good question that could be asked at the interview, because it is simple enough for you to write on a white board, but difficult enough for him to knock someone over if they did not think about This is thorough enough. In addition, you can also use two different answers, which differ significantly from the implementation.

Questions for ordering
If order matters, then any solution must allow zero for any of the variables; thus, the most direct solution would be as follows:

 public class Combos { public static void main() { long counter = 0; for (int a = 0; a <= 500; a++) { for (int b = 0; b <= (500 - a); b++) { for (int c = 0; c <= (500 - a - b); c++) { for (int d = 0; d <= (500 - a - b - c); d++) { counter++; } } } } System.out.println(counter); } } 

Which returns 2656615626.

Order doesn't matter
If the order does not matter, then the solution is not much more complicated, since you just need to make sure that zero is not possible if the sum is not already found.

 public class Combos { public static void main() { long counter = 0; for (int a = 1; a <= 500; a++) { for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) { for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) { for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) { counter++; } } } } System.out.println(counter); } } 

Which returns 2573155876.

Answer 4

I solved this problem for my dad a couple of months ago ... expand for your use. They are usually one time, so I did not go for the most reusable ...

a + b + c + d = sum

i = number of combinations

  for (a=0;a<=sum;a++) { for (b = 0; b <= (sum - a); b++) { for (c = 0; c <= (sum - a - b); c++) { //d = sum - a - b - c; i++ } } } 

Answer 5

One way to address the problem is to:

Firstly, a can be any value from 0 to 500. Then, if it follows that b + c + d + e = 500-a. This reduces the problem by one variable. Repair to completion.

For example, if a is 500, then b + c + d + e = 0, which means that for the case a = 500 there is only one combination of values ​​for b, c, d and e.

If a is 300, then b + c + d + e = 200, which is actually the same problem as the original problem, just reduced by one variable.

Note. As Chris points out, this is a terrible way to actually try to solve the problem.

link text

Answer 6

If they are real numbers, then they are infinite ... otherwise it is a little more complicated.

(OK, for any computer representation of a real number, there would be a finite number ... but it would be big!)

Answer 7

It has general formulas if a + b + c + d = N
Then the number of non-negative integral solutions will be C(N + number_of_variable - 1, N)

Answer 8

@ Chris Conway answers correctly. I checked with a simple code that works for smaller amounts.

  long counter = 0; int sum=25; for (int a = 0; a <= sum; a++) { for (int b = 0; b <= sum ; b++) { for (int c = 0; c <= sum; c++) { for (int d = 0; d <= sum; d++) { for (int e = 0; e <= sum; e++) { if ((a+b+c+d+e)==sum) counter=counter+1L; } } } } } System.out.println("counter e "+counter); 

Answer 9

The answer in mathematics is 504! / (500! * 4!).

Formally, for x1 + x2 + ... xk = n, the number of combinations of a non-negative number x1, ... xk is a binomial coefficient: a (k-1) -combination from a set containing (n + k -1).

The intuition is to select (k-1) points from (n + k-1) points and use the number of points between two selected points to represent the number in x1, ... xk.

Sorry for the poor math edition for my fist, responding to a stack overflow.

Just a test for code block

 Just a test for code block Just a test for code block 

Answer 10

Including negatives? Endless.

Including only positive results? In this case, they will not be called "whole", but "natural". In this case ... I cannot solve this, I would like to, but my math is too rusty. There is probably some crazy integral way to solve this problem. I can give some pointers for math.

is x the end result, range a will be from 0 to x, range b will be from 0 to (x - a), range c will be from 0 to (x - a - b), etc. until e.

The answer is the sum of all these possibilities.

I am trying to find a more direct formula on Google, but today I am really low on my Google Fu ...