[Python] How to get the <i>th element of the <n>th permutation of a sequence directly (without...

Let say we have a string "ABCD" and we want to retrieve the letter in the i-th position from the n-th permutation of the string.

In this example, I know there are factorial(4) = 24 permutations and the list can be retrieved easily with itertools.permutations, which will give this:

['ABCD', 'ABDC', 'ACBD', 'ACDB', 'ADBC', 'ADCB', 'BACD', 'BADC', 'BCAD', 'BCDA', 'BDAC', 'BDCA', 'CABD', 'CADB', 'CBAD', 'CBDA', 'CDAB', 'CDBA', 'DABC', 'DACB', 'DBAC', 'DBCA', 'DCAB', 'DCBA']
​

So the function f I am looking for should return:

f(0, n) == ['A', 'A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', 'B', 'C', 'C', 'C', 'C', 'C', 'C', 'D', 'D', 'D', 'D', 'D', 'D'][n]

f(1, n) == ['B', 'B', 'C', 'C', 'D', 'D', 'A', 'A', 'C', 'C', 'D', 'D', 'A', 'A', 'B', 'B', 'D', 'D', 'A', 'A', 'B', 'B', 'C', 'C'][n]

f(2, n) == ['C', 'D', 'B', 'D', 'B', 'C', 'C', 'D', 'A', 'D', 'A', 'C', 'B', 'D', 'A', 'D', 'A', 'B', 'B', 'C', 'A', 'C', 'A', 'B'][n]

f(3, n) == ['D', 'C', 'D', 'B', 'C', 'B', 'D', 'C', 'D', 'A', 'C', 'A', 'D', 'B', 'D', 'A', 'B', 'A', 'C', 'B', 'C', 'A', 'B', 'A'][n]
​

It's pretty easy for i == 0, we have f(0, n) == "ABCD"[n // 6] but finding a pattern when i increases is more and more complicated.

I don't care at all how the permutations are ordered so maybe a common pattern for every values of i can be found easily...

I'm planning to use this with a set of 256 elements and factorial(256) permutations, so computing the permutations is not an option.

Edit: I already have a function for this but it's too slow and I was wondering if some equivalent result can be found with a straightforward formula using for example bitwise operations...

Edit-2: Here is the current best solution thanks to @rici:

f = [factorial(i) for i in range(256)]

def _getElt(k, i):
"""
Returns the <i>th element of the <k>th permutation of 0..255
"""
table = list(range(256))

for j in range(255, 254-i, -1):
r, k = divmod(k, f[j])
perm[j], perm[r] = perm[r], perm[j]
return perm[255 - i]


Edit-3: Here is a another approach using polynomial approximations to recreate the permutations, so a different formulation of the problem could be "how to recreate the polynomial's i-th coefficient for the n-th permutation?".

This is a list of n, permutation, polynomial's coefficient (and finally the permutation rebuild from the polynomial's coefficients) for N=4:

0 [0, 1, 2, 3] [Fraction(0, 1), Fraction(1, 1), Fraction(0, 1), Fraction(0, 1)] [0, 1, 2, 3]

1 [0, 1, 3, 2] [Fraction(0, 1), Fraction(-3, 4), Fraction(5, 2), Fraction(-2, 3)] [0, 1, 3, 2]

2 [0, 2, 1, 3] [Fraction(0, 1), Fraction(11, 2), Fraction(-9, 2), Fraction(1, 1)] [0, 2, 1, 3]

3 [0, 2, 3, 1] [Fraction(0, 1), Fraction(7, 4), Fraction(1, 2), Fraction(-1, 3)] [0, 2, 3, 1]

4 [0, 3, 1, 2] [Fraction(0, 1), Fraction(33, 4), Fraction(-13, 2), Fraction(4, 3)] [0, 3, 1, 2]

5 [0, 3, 2, 1] [Fraction(0, 1), Fraction(19, 3), Fraction(-4, 1), Fraction(2, 3)] [0, 3, 2, 1]

6 [1, 0, 2, 3] [Fraction(1, 1), Fraction(-15, 4), Fraction(7, 2), Fraction(-2, 3)] [1, 0, 2, 3]

7 [1, 0, 3, 2] [Fraction(1, 1), Fraction(-17, 3), Fraction(6, 1), Fraction(-4, 3)] [1, 0, 3, 2]

8 [1, 2, 0, 3] [Fraction(1, 1), Fraction(21, 4), Fraction(-11, 2), Fraction(4, 3)] [1, 2, 0, 3]

9 [1, 2, 3, 0] [Fraction(1, 1), Fraction(-1, 3), Fraction(2, 1), Fraction(-2, 3)] [1, 2, 3, 0]

10 [1, 3, 0, 2] [Fraction(1, 1), Fraction(31, 4), Fraction(-15, 2), Fraction(5, 3)] [1, 3, 0, 2]

11 [1, 3, 2, 0] [Fraction(1, 1), Fraction(17, 4), Fraction(-5, 2), Fraction(1, 3)] [1, 3, 2, 0]

12 [2, 0, 1, 3] [Fraction(2, 1), Fraction(-17, 4), Fraction(5, 2), Fraction(-1, 3)] [2, 0, 1, 3]

13 [2, 0, 3, 1] [Fraction(2, 1), Fraction(-31, 4), Fraction(15, 2), Fraction(-5, 3)] [2, 0, 3, 1]

14 [2, 1, 0, 3] [Fraction(2, 1), Fraction(1, 3), Fraction(-2, 1), Fraction(2, 3)] [2, 1, 0, 3]

15 [2, 1, 3, 0] [Fraction(2, 1), Fraction(-21, 4), Fraction(11, 2), Fraction(-4, 3)] [2, 1, 3, 0]

16 [2, 3, 0, 1] [Fraction(2, 1), Fraction(17, 3), Fraction(-6, 1), Fraction(4, 3)] [2, 3, 0, 1]

17 [2, 3, 1, 0] [Fraction(2, 1), Fraction(15, 4), Fraction(-7, 2), Fraction(2, 3)] [2, 3, 1, 0]

18 [3, 0, 1, 2] [Fraction(3, 1), Fraction(-19, 3), Fraction(4, 1), Fraction(-2, 3)] [3, 0, 1, 2]

19 [3, 0, 2, 1] [Fraction(3, 1), Fraction(-33, 4), Fraction(13, 2), Fraction(-4, 3)] [3, 0, 2, 1]

20 [3, 1, 0, 2] [Fraction(3, 1), Fraction(-7, 4), Fraction(-1, 2), Fraction(1, 3)] [3, 1, 0, 2]

21 [3, 1, 2, 0] [Fraction(3, 1), Fraction(-11, 2), Fraction(9, 2), Fraction(-1, 1)] [3, 1, 2, 0]

22 [3, 2, 0, 1] [Fraction(3, 1), Fraction(3, 4), Fraction(-5, 2), Fraction(2, 3)] [3, 2, 0, 1]

23 [3, 2, 1, 0] [Fraction(3, 1), Fraction(-1, 1), Fraction(0, 1), Fraction(0, 1)] [3, 2, 1, 0]
​

We can see clearly that there is a symmetry: coefs = [3 - coefs[23-i][0]] + [-c for c in coefs[23-i][1:]] so it's a way to explore but I have no clue that it's possible.

Continue reading...