Permutation number

A permutation number identifies one permutation in a specified ordering. For n distinct items, there are n! possible permutations, so the numbers run from 0 to n!−1. The ordering matters: the same number can identify different permutations under lexicographic, Fisher–Yates, and change-ringing schemes. An index is useful when you want one permutation without generating every preceding one. section 6.2 section 6.2.3 section 6.2.4

For lexicographic order, start with the remaining items 0 through n−1. Divide p by (n−1)!: the quotient selects the first item, and the remainder selects a permutation of the other items. Remove the chosen item and repeat with the smaller factorial. With n = 4, number 9 selects 1 first, then 2, 3, and 0, giving 1230. This assumes p is in range and the starting integers are distinct; the resulting integer permutation can also serve as indices into another list. section 6.2.1 section 6.2

The four-by-six table groups the 24 lexicographic permutations of four items by first item, making the quotient the row and the remainder the column. section 6.2.1

Those successive quotients are the digits of p in factorial base. For example, 19 = 3×3! + 0×2! + 1×1! + 0×0!, written 3010. Reading the digits left to right as positions in the shrinking remaining list produces the lexicographic permutation 3021. The rightmost factorial-base digit is always 0. section 6.2.2

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;
    }
}

GetLexiPermutation implements the repeated division and removal in C#, using BigInteger for the permutation number and factorial. section 6.2.1

Other orderings give the number a different decoding rule. A Fisher–Yates-style generator uses the same factorial-derived choices but swaps items instead of removing them. It is cheaper when lexicographic order is unnecessary, but its numbering differs: number 4 gives 0321 rather than the lexicographic 0312. Change ringing instead computes a column p/n, recursively finds that smaller permutation, and uses p%n to position the new item; the insertion direction alternates by column. section 6.2.3 section 6.2.4