Combination By Lexicographical Index
This online calculator finds combination by index in lexicographically ordered set.
In mathematics, the lexicographic or lexicographical order (aka lexical order, dictionary order or alphabetical order) is a way sequences (f.e. words) are alphabetically ordered based on the alphabetical order of their components (letters). It is often used in combinatorics, for example, for producing all possible combinations  they are generated in lexicographical order.
Let's suppose we have set of 5 elements { 0 1 2 3 4 } and want to generate all 3combinations. There are 10 combinations total, and here they are in lexicographical order
0: { 0 1 2 }
1: { 0 1 3 }
2: { 0 1 4 }
3: { 0 2 3 }
4: { 0 2 4 }
5: { 0 3 4 }
6: { 1 2 3 }
7: { 1 2 4 }
8: { 1 3 4 }
9: { 2 3 4 }
If you want to generate all possible combinations in lexicographical order you can use Combinatorics. Generator of combinations. calculator
So, this calculator outputs combination by its index in lexicographically ordered list of all combinations. Of course it does this without computing all the combinations for the sake of efficiency. You can find algorithm description below the calculator.
Note: index is ZERObased.
Finding the combination by its lexicographical index
This calculator uses algorithm described by James McCaffrey^{1}.
Let's use the following notations and definitions:
 n  number of elements in the set, f.e. 5
 k  number of elements in combination, f.e. 3
 N  total number of combinations, f.e. 10
 index of combination in lexicographical list, zerobased, from 0 to N1, f.e. 0 ... 9
 dual index  opposite index, sum of index and its opposite gives N1, f.e. for the index 1 the dual index is 8
Algorithm
 Find dual index for given index i by computing (N1)  i
 Find combinadic of dual index, see Combinatorial number system
 Invert each combinadic coefficient c by computing (n1)  c
 The resulting coefficients represent the desired combination.

James McCaffrey. Generating the mth Lexicographical Element of a Mathematical Combination. MSDN Magazine, July 2004 ↩
Comments