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 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.

PLANETCALC, Combination By Index

Combination By Index

Combination
 
Total number of combinations
 

Finding the combination by its lexicographical index

This calculator uses an algorithm described by James McCaffrey1.

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.

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

URL copied to clipboard
PLANETCALC, Combination By Lexicographical Index

Comments