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 (i.e. words) are alphabetically ordered based on the alphabetical order of their components (letters). It is often used in combinatorics to produce all possible combinations  they are generated in lexicographical order.
Let's suppose we have a set of 5 elements { 0 1 2 3 4 } and want to generate all 3combinations. There are 10 combinations, 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 Combinations generator calculator
So, this calculator outputs a combination by its index in a lexicographically ordered list of all combinations. Of course, it does this without computing all the combinations for the sake of efficiency. You can find the algorithm description below the calculator.
Note: index is ZERObased.
Finding the combination by its lexicographical index
This calculator uses an 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 the lexicographical list, zerobased, from 0 to N1, f.e. 0 ... 9
 dual index  opposite index, the sum of the 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 the 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