Generate one permutation from an index

Question

Is there an efficient algorithm to generate a permutation from one index provided? The permutations do not need to have any specific ordering and it just needs to return every permutation once per every possible index. The set I wish to permute is all integers from 0~255.

Answer 1

If I understand the question correctly, the problem is as follows: You are given two integers n and k, and you want to find the kth permutation of n integers. You don't care about it being the kth lexicographical permutation, but it's just easier to be lexicographical so let's stick with that.

This is not too bad to compute. The base permutation is 1,2,3,4...n. This is the k=0 case. Consider what happens if you were to swap the 1 and 2: by moving the 1, you are passing up every single permutation where 1 goes first, and there are (n-1)! of those (since you could have permuted 2,3,4..n if you fixed the 1 in place). Thus, the algorithm is as follows:

for i from 1 to n:
    j = k / (n-i)! // integer division, so rounded down
    k -= j * (n-i)!
    place down the jth unplaced number

This will iteratively produce the kth lexicographical permutation, since it repeatedly solves a sub-problem with a smaller set of numbers to place, and decrementing k along the way.

Answer 2

There is an implementation in python in module more-itertools: nth_permutation.

Here is an implementation, adapted from the code of more_itertools.nth_permutation:

from sympy import factorial

def nth_permutation(iterable, index):
    pool = list(iterable)
    n = len(pool)
    c = factorial(n)
    index = index % c
    result = [0] * n
    q = index
    for d in range(1, n + 1):
        q, i = divmod(q, d)
        if 0 <= n - d < n:
            result[n - d] = i
        if q == 0:
            break
    return tuple(map(pool.pop, result))

print( nth_permutation(range(6), 360) )
# (3, 0, 1, 2, 4, 5)