Combinatorics. The generator of combinations.

This calculator which generates possible combinations of m elements from the set of element with size n.

The number of possible combinations, as shown in Combinatorics – combinations, arrangements and permutations, is
C_{n}^m=\frac{n!}{m!(n-m)!}.
The description of the generator algorithm is below the calculator.

PLANETCALC, Combinatorics. Generator of combinations.

Combinatorics. Generator of combinations.

Set

Value
Items per page:

The file is very large. Browser slowdown may occur during loading and creation.

Combinations generation algorithm

Combinations are generated in lexicographical order. Algorithms use indexes of the elements of the set.
Here is how it works on example:
Suppose we have a set of 5 elements with indexes 1 2 3 4 5 (starting from 1), and we need to generate all combination size m = 3.
First, we initialize the first combination size m - indexes in ascending order
1 2 3
We start by checking the last element (i = 3). If its value is less than n - m + i, it is incremented by 1.
1 2 4
Again we check the last element, and since it is still less than n - m + i, it is incremented by 1.
1 2 5
Now it has the maximum allowed value: n - m + i = 5 - 3 + 3 = 5, so we move on to the previous element (i = 2).
If its value less than n - m + i, it is incremented by 1, and all following elements are set to value of their previous neighbor plus 1
1 (2+1)3 (3+1)4 = 1 3 4
Then we again start from the last element i = 3
1 3 5
Back to i = 2
1 4 5
Now it finally equals n - m + i = 5 - 3 + 2 = 4, so we can move to first element (i = 1)
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
And then,
2 3 5
2 4 5
3 4 5 - last combination since all values are set to the maximum possible values of n - m + i.

URL copied to clipboard
PLANETCALC, Combinatorics. The generator of combinations.

Comments