Combinations generator
This combinations calculator generates all possible combinations of m elements from the set of n elements.
For example, if you have a set from 3 elements, {A, B, C}, the all possible combinations of size 2 will be {A,B}, {A,C} and {B,C}. That is, combination here refers to the combination of n things taken m at a time without repetition. The total number of possible combinations, as shown in Combinatorics – combinations, arrangements and permutations, is
.
To use the combinations generator below, you need to fill the set (by default it consists of A, B, C, D, and E elements), and enter combination size. All combinations will be generated using a lexicographic algorithm. The description of the algorithm used by the generator can be found below the calculator.
Combinations generator algorithm
Combinations are generated in lexicographical order. The algorithm uses 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 combinations of size m = 3.
First, we initialize the first combination of size m - with indexes in ascending order
1 2 3
Then we check 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 - and it is the last combination since all values are set to the maximum possible value of n - m + i.
Comentários