Lesson 6

Now let's figure out how to find the permutation by its index \(0 \le m < n!\). For each \(i \in \{0,1,\dotsc,n-1\}\) there are exactly \((n-1)!\) permutations starting with \(i\), and they have indices from \(i \cdot (n-1)!\) to \((i+1) \cdot (n-1)! - 1\). Therefore, the first element of the desired permutation is \(\lfloor \frac{m}{(n-1)!}\rfloor\). We can continue recursively. We just need to subtract \(i(n-1)!\) from \(m\) and remember that element \(i\) has already been used.

from itertools import permutations
from math import factorial


def permutation_by_index(elements, index):
    assert 0 <= index < factorial(len(elements))
    remaining_elements, permutation = list(elements), []

    while remaining_elements:
        i = index // factorial(len(remaining_elements) - 1)
        index -= i * factorial(len(remaining_elements) - 1)
        permutation.append(remaining_elements.pop(i))

    return permutation


elements = 'abcd'
for i, perm in enumerate(permutations(elements)):
    print(i, perm, permutation_by_index(elements, i))

0 ('a', 'b', 'c', 'd') ['a', 'b', 'c', 'd']
1 ('a', 'b', 'd', 'c') ['a', 'b', 'd', 'c']
2 ('a', 'c', 'b', 'd') ['a', 'c', 'b', 'd']
3 ('a', 'c', 'd', 'b') ['a', 'c', 'd', 'b']
4 ('a', 'd', 'b', 'c') ['a', 'd', 'b', 'c']
5 ('a', 'd', 'c', 'b') ['a', 'd', 'c', 'b']
6 ('b', 'a', 'c', 'd') ['b', 'a', 'c', 'd']
7 ('b', 'a', 'd', 'c') ['b', 'a', 'd', 'c']
8 ('b', 'c', 'a', 'd') ['b', 'c', 'a', 'd']
9 ('b', 'c', 'd', 'a') ['b', 'c', 'd', 'a']
10 ('b', 'd', 'a', 'c') ['b', 'd', 'a', 'c']
11 ('b', 'd', 'c', 'a') ['b', 'd', 'c', 'a']
12 ('c', 'a', 'b', 'd') ['c', 'a', 'b', 'd']
13 ('c', 'a', 'd', 'b') ['c', 'a', 'd', 'b']
14 ('c', 'b', 'a', 'd') ['c', 'b', 'a', 'd']
15 ('c', 'b', 'd', 'a') ['c', 'b', 'd', 'a']
16 ('c', 'd', 'a', 'b') ['c', 'd', 'a', 'b']
17 ('c', 'd', 'b', 'a') ['c', 'd', 'b', 'a']
18 ('d', 'a', 'b', 'c') ['d', 'a', 'b', 'c']
19 ('d', 'a', 'c', 'b') ['d', 'a', 'c', 'b']
20 ('d', 'b', 'a', 'c') ['d', 'b', 'a', 'c']
21 ('d', 'b', 'c', 'a') ['d', 'b', 'c', 'a']
22 ('d', 'c', 'a', 'b') ['d', 'c', 'a', 'b']
23 ('d', 'c', 'b', 'a') ['d', 'c', 'b', 'a']