All possible combinations of n elements randomly selected from a set of x elements (algorithm)

Question

I have a set of elements of row x, for example ("A", "B", "C", "D", "E", "F") I need to know a formula that calculates how many combinations of n elements and which algorithm generates all possible combinations, for example, if we need to select 4 items from a list at random. these 4 elements can be: ("A", "B", "C", "D") or ("A", "B", "C", "E") or ("A", "B" , "C", "F") or ("A", "B", "D", "E") ... etc. I need a formula that calculates how many sets of elements will be generated without repeating, that is, we consider ("A", "B", "C", "D") as one of the above combinations, we cannot consider the same ones elements as another final combination with replacing items in a set of types ("A", "B", "D", "C") I also need an algorithm that generates all possible combinations in any programming language. [C #, VB.NET, Java, C ++]

Thanks for any help.

Answer 1

Choosing p from n elements, this is a formula to tell you how many combinations there are.

n! n choose p = ----------- p! (np)! 

Google Calculator will do the math for you:

http://www.google.com/search?q=6+choose+4

6 select 4 = 15

Answer 2

The formula for the combination you are describing is given in @Mark Harrison's answer. However, plug in this equation and it will explode because the math is designed to be canceled.

For example, 50 select 49 - this is the same as choosing which item to exclude, so there are 50 options. However, the formula will require you to calculate

  50! 3.04140932e64 -------- = ----------------- = 50 1! * 49! 1 * 6.08281864e62 

The equation you really want for x selects y,

 x * (x-1) * ... * (x-n+1) ------------------------- n * (n-1) * ... * 2 * 1 

Simple C code [note that this optimizes that C (x, y) = C (x, xy) - this should be easily seen from the combination formula:

 int c(int x, int y) { int num = 1, denom = 1; int i; if (y > xy) y = x - y; for (i = 0; i < y; ++i) { num *= (x - i); denom *= (y - i); } return num/denom; } 

So, if you need all possible combinations of letters "ABCDEF", where you select 4 letters, that is, c(6,4) .

Answer 3

I need an algorithm that generates all possible combinations in any programming language.

Ok, here is a single line solution in Haskell:

 import Data.List (subsequences) n `outOf` xs = filter ((n ==) . length) (subsequences xs) test = 4 `outOf` ["A", "B", "C", "D", "E", "F"] *Main> test [["A","B","C","D"],["A","B","C","E"],["A","B","D","E"],["A","C","D","E"],["B","C ","D","E"],["A","B","C","F"],["A","B","D","F"],["A","C","D","F"],["B","C","D","F "],["A","B","E","F"],["A","C","E","F"],["B","C","E","F"],["A","D","E","F"],["B", "D","E","F"],["C","D","E","F"]] *Main> length test 15 

Answer 4

You need the Binomial Theorem , and you need nested loops. As for the implementation in one of your programming languages, writing is not so difficult. If you look around, you will find that this question is regularly asked on SO, and you will find that people vote to close your question for this reason.

Answer 5

You can also go lexicographical ordering .

Something like that:

 #include <stdio.h> void print(const int *v, const int size) { int i; if (v != 0) { for (i = 0; i < size; i++) { printf("%4d", v[i] ); } printf("\n"); } } // print void visit(int *Value, int N, int k) { int i; static level = -1; level = level+1; Value[k] = level; if (level == N) print(Value, N); else for (i = 0; i < N; i++) if (Value[i] == 0) visit(Value, N, i); level = level-1; Value[k] = 0; } main() { const int N = 4; int Value[N]; int i; for (i = 0; i < N; i++) { Value[i] = 0; } visit(Value, N, 0); } 

Answer 6

You can calculate the number of combinations using the Pascal Triangle . To find the actual combinations, you can use regular recursion.

Answer 7

Yes, the Pascal triangle works.

 int dp[MAX_X][MAX_Y] = {0}; dp[0][0] = 1; for (int i = 1; i <= X; i++) { dp[i][0] = dp[i][i] = 0; for (int j = 1; j < min(i, Y + 1); j++) dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; } print(dp[X][Y]) 

Alternatively, you can do something using the U-turn trick.

And again, I think this formula works better if the values ​​do not get too large.