Combination By Lexicographical Index

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 3-combinations. 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 ZERO-based.

Combination By Index

Set size n

Combination size k

Lexicographical index

Calculate

Combination

 

Total number of combinations

 

 Link  Save  Widget

Finding the combination by its lexicographical index

This calculator uses an algorithm described by James McCaffrey¹.

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, zero-based, from 0 to N-1, f.e. 0 ... 9
• dual index - opposite index, the sum of the index and its opposite gives N-1, f.e. for the index 1; the dual index is 8

Algorithm

1. Find dual index for given index i by computing (N-1) - i
2. Find combinadic of the dual index, see Combinatorial number system
3. Invert each combinadic coefficient c by computing (n-1) - c
4. The resulting coefficients represent the desired combination.