python - i-th element of k-th permutation

Question

Is there a fast algorithm to compute the i-th element (0 <= i < n) of the k-th permutation (0 <= k < n!) of the sequence 0..n-1?

Any order of the permutations may be chosen, it does not have to be lexicographical. There are algorithms that construct the k-th permutation in O(n) (see below). But here the complete permutation is not needed, just its i-th element. Are there algorithms that can do better than O(n)?

Is there an algorithm that has a space complexity less than O(n)?

There are algorithms that construct the k-th permutation by working on an array of size n (see below), but the space requirements might be undesirable for large n. Is there an algorithm that needs less space, especially when only the i-th element is needed?

---

Algorithm that constructs the k-th permutation of the sequence 0..n-1 with a time and space complexity of O(n):

def kth_permutation(n, k):
    p = range(n)
    while n > 0:
        p[n - 1], p[k % n] = p[k % n], p[n - 1]
        k /= n
        n -= 1
    return p

Source: http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Answer 1

You probably cannot get the i'th digit of the k'th permutation of n elements in O(n) time or space, because representing the number k itself requires O(log(n!)) = O(n log n) bits, and any manipulations with it have corresponding time complexity.