Lexicographic ordering puts sequences in dictionary order: compare elements from left to right, and let the first difference decide. Thus COATS comes before TACOS. The underlying element order determines what “before” means. section 6.2.1
Finding the next permutation
The permutation immediately after COATS is COSAT. Find the rightmost element smaller than its neighbor to the right (A), swap it with the rightmost greater element (S), then reverse the suffix. If no such element exists, the sequence is already in reverse order and has no successor. section 6.2.1
A mutable IList<T> can repeat that successor operation to enumerate permutations; starting in sorted order enumerates them all. Duplicate elements are allowed. Lexicographic order also gives each permutation a position: for distinct integers from 0 to n−1, factorial-sized groups determine each successive element of the permutation at a given position. section 6.2.1 section 6.4
Listing 6.9 Generating a permutation from a permutation number
using System.Numerics;
static IList<int> GetLexiPermutation(int n, BigInteger p) #1
{
var remaining = new List<int>(Enumerable.Range(0, n));
var result = new List<int>(n); #2
var f = n.Factorial();
for (int cur = n; cur > 0; cur -= 1)
{
f /= cur; #3
var r = (int)(p / f); #4
p %= f;
result.Add(remaining[r]);
remaining.RemoveAt(r);
}
return result;
}
static class Extensions
{
public static BigInteger Factorial(this int n) #5
{
BigInteger result = 1;
for(int i = 2; i <= n; i += 1)
result *= i;
return result;
}
}
The C# implementation selects each element of a numbered permutation by dividing its remaining position by a factorial and removing the selected element from the available list. section 6.2.1
Combinations expose a useful twist. When a combination is written as increasing integers, it is convenient to compare those integers from right to left. For four-element combinations drawn from 0 through 5, 1245 is followed by 0345: increment the element that can advance, then reset the elements to its left to their lowest values. This looks unlike ordinary dictionary order because the comparison direction has changed. section 6.3.1
0123 0124 0134 0234 1234 0125 0135 0235 1235 0145 0245 1245 0345 1345 2345
The full 6-choose-4 sequence makes the right-to-left ordering visible, including the transition from 1245 to 0345. section 6.3.1
Ordering also makes direct access possible. Number the k-element combinations from 0 to n choose k minus 1. To find one by number, split the ordered list into combinations without n−1 and those ending in n−1; the first group has (n−1) choose k members. Recursing into the appropriate group avoids enumerating every preceding combination. A sorted-input Cartesian product likewise emits its output sequences in lexicographic order. section 6.3.2 section 6.1.2
