Get reference code
Appearance
Sample
StudyMath

Combinatorics. Generator of combinations.

Combinatorics. Generator of combinations of m from n.
Timur2014-07-21 07:28:42

This calculator which generates possible combinations of m elements from the set of element with size n. Number of possible combinations, as shown in Combinatorics. Combinations, arrangements and permutations is
C_{n}^m=\frac{n!}{m!(n-m)!}

The description of generator algorithm is below the calculator

Combinatorics. Generator of combinations.Creative Commons Attribution/Share-Alike License 3.0 (Unported)
Set
Import data.
"One of the following characters is used to separate data fields: tab, semicolon (;) or comma(,)": 
Add Import data. Clear table
Combinations:

Algorithm

Combinations are generated in lexicographical order. Algorithms uses indexes of the elements of 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 first combination size m - indexes in ascending order
1 2 3
We start from checking the last element (i.e. i = 3). If its value less than n - m + i, it is incremented by 1.
1 2 4
Again we check 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.

Request a calculator
View all calculators
(512 calculators in total. )

Comments