How to get the <i>th element of the <n>th permutation of a sequence directly (without any recursivity)?

Question

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[i] = [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.

Answer 1

You can find the n-th permutation by doing repeated euclidean division (quotient and remainder, aka divmod) and keeping track of what letters you pick. You can then pick the i-th letter from that permutation.

Let S be a copy of the initial string, L the length of that string and P the number of permutations (L!). T will be the n-th permutation of S, constructed step-by-step.
Example: S = "ABCD", L = 4, and P = 24. Let's take n = 15 for the example. T should be "CBDA" at the end.

Set P = P/L. Compute divmod(n, P), let q be the quotient (n/P) and r the remainder (n%P). Remove the q-th letter from S and append it to T. Set n = r, decrement L, and repeat until L = 0.
Example:
1) P = 24/4 = 6, q = 15/6 = 2, r = 15%6 = 3, S = "ABD", T = "C", n = r = 3, L = 3.
2) P = 6/3 = 2, q = 3/2 = 1, r = 3%2 = 1, S = "AD", T = "CB", n = r = 1, L = 2.
3) P = 2/2 = 1, q = 1/1 = 1, r = 1%1 = 0, S = "A", T = "CBD", n = r = 0, L = 1.
4) P = 1/1 = 1, q = 0/1 = 0, r = 0%1 = 0, S = "", T = "CBDA", n = r = 0, L = 0.

Since you only want the i-th letter, you can stop whenever the length of T equals i+1 and take that last letter.

I won't try to code this in Python because it's been too long since I've touched Python, but here is a demo in C++.

Answer 2

Sorry, for my Python. The idea is that letter at every positions repeats (number_of_pos - pos)! times.

E.g. ABCD, letter at the first position would repeat 3! times. So, by dividing n by this factorial we now which letter is in the first position. To find letter in the second position we need to remove this letter from the set (assign 0 instead) and update n with n - n % 3! to now index of letter in the second position. When applying this index we need to take care not to count letter which is in the first position.

Complexity is O(kPosCount * kPosCount).

#include <array>
#include <iostream>

const int kPosCount = 4;
const std::array<int, kPosCount> factorial = { 1,1,2,6 };
const std::array<int, kPosCount> kLetters = { 'A', 'B', 'C', 'D' };

char f(int pos, int n) {
    assert(pos < kPosCount);
    std::array<int, kPosCount> letters = kLetters;

    int res = 0;
    for (int i = 0; i <= pos; ++i) {
        const int letter = n / factorial[kPosCount - i - 1];
        int j = 0;
        for (int stillThere = 0; j < kPosCount; ++j) {
            if (letters[j] != 0) {
                if (stillThere == letter) {
                    break;
                }
                ++stillThere;
            }
        }
        letters[j] = 0;
        res = j;
        n %= factorial[kPosCount - i - 1];
    }
    return kLetters[res];
}

int main() {
    const int kMaxN = factorial.back() * kPosCount;
    for (int i = 0; i < kPosCount; ++i) {
        for (int j = 0; j < kMaxN; ++j) {
            std::cout << f(i, j) << " ";
        }
        std::cout << std::endl;
    }
}

Answer 3

Here's a version of your function with a different permutation order. I didn't force the size of the permutation to be 256 here, so you have to supply it as the first argument.

def elt(n,k,i):
  """Returns element i of permutation k from permutations of length n"""
  perm = [*range(n)]
  for j in range(i+1):
    k, r = divmod(k, n-j)
    perm[j], perm[j+r] = perm[j+r], perm[j]
  return perm[i]

That has two differences from your code.

First, the digits are carved off of the index from right-to-left, which means that the bignum divmods are all divmods by a small dividend. I thought that would be faster than using a bignum dividend, but it turns out to be significantly slower. However, it does avoid having to precompute the factorials.

Second, rather than doing a series of pops from the middle of a table, which is going to be of quadratic complexity because the pop operation is O(n), I just swap each element with some forward element. That's significantly faster, although the bignum arithmetic dominates the computation.

In effect, elt(n,k,i) does the first i steps in a Fisher-Yates shuffle of range(n) using the mixed-base decomposition of k as what would be the random values in a random shuffle. Since the F-Y shuffle produces a different result for each possible sequence of random values, and the mixed-base decomposition of k produces a different sequence for each different value of k, all permutations will be generated.

Here's what the order looks like for n=4:

>>> print('\n'.join(' '.join(str(elt(4, k, i)) for i in range(4))
                    for k in range(factorial(4))))
0 1 2 3
1 0 2 3
2 1 0 3
3 1 2 0
0 2 1 3
1 2 0 3
2 0 1 3
3 2 1 0
0 3 2 1
1 3 2 0
2 3 0 1
3 0 2 1
0 1 3 2
1 0 3 2
2 1 3 0
3 1 0 2
0 2 3 1
1 2 3 0
2 0 3 1
3 2 0 1
0 3 1 2
1 3 0 2
2 3 1 0
3 0 1 2

To actually speed up the function, I reintroduced the precomputed factorials (as an local variable which is extended as necessary). I also micro-optimised the inner loop by removing as much arithmetic as possible, which meant doing the F-Y shuffle from back to front. This results in yet another permutation order; see below for an example.

The final optimised function is about 15% faster than the version in the question (that is, it takes about 85% of the time to do a simple benchmark).

def elt_opt(n, k, i, fact=[1]):
    """Returns element i of permutation k from permutations of length n.
       Let the last argument default.
    """
    while len(fact) < n: fact.append(fact[-1]*len(fact))
    perm = list(range(n))
    for j in range(n-1, n-2-i, -1):
        r, k = divmod(k, fact[j])
        perm[j], perm[r] = perm[r], perm[j]
    return perm[n-i-1]

Permutation order:

>>> print('\n'.join(' '.join(str(elt_opt(4, k, i)) for i in range(4))
                    for k in range(factorial(4))))
0 3 2 1
0 3 1 2
0 1 3 2
0 1 2 3
0 2 3 1
0 2 1 3
1 0 2 3
1 0 3 2
1 3 0 2
1 3 2 0
1 2 0 3
1 2 3 0
2 0 3 1
2 0 1 3
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 2 1
3 0 1 2
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0