Lesson 5

As we can see, the index of a permutation \(p\) is the number of permutations that come before \(p\) in such a list. Any such permutation matches \(p\) completely up to some position \(0 \le k < n\), has an element less than \(p[k]\) at position \(k\), and the remaining elements (which are \(n-k-1\)) are arranged in any order. This gives us the following algorithm:

from itertools import permutations
from math import factorial


def permutation_index(perm):
    n = len(perm)
    assert sorted(perm) == sorted(range(n))

    result = 0
    for k in range(n):
        for x in range(perm[k]):
            if x not in perm[:k]:
                result += factorial(n - k - 1)

    return result


for i, perm in enumerate(permutations(range(3))):
    print(i, perm, permutation_index(perm))

0 (0, 1, 2) 0
1 (0, 2, 1) 1
2 (1, 0, 2) 2
3 (1, 2, 0) 3
4 (2, 0, 1) 4
5 (2, 1, 0) 5