homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightCombinatorics

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

PLANETCALC, Combination By Index

Combination By Index

Combination
 
Total number of combinations
 

Finding the combination by its lexicographical index

This calculator uses 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 lexicographical list, zero-based, from 0 to N-1, f.e. 0 ... 9
  • dual index - opposite index, sum of 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 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
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Combination By Lexicographical Index

Comments