Есть ли быстрый алгоритм для вычисления i-го элемента?(0 <= i < n) k-й перестановки(0 <= k < n!) последовательности 0..n-1?

Любой порядок перестановок может быть выбран, он не должен быть лексикографическим. Есть алгоритмы, которые создаютkая перестановка вO(n) (увидеть ниже). Но здесь полная перестановка не нужна, просто ееiэлемент Есть ли алгоритмы, которые могут сделать лучше, чемO(n)?

Есть ли алгоритм, который имеет сложность пространства меньше, чем O (n)?

Есть алгоритмы, которые создаютkая перестановка, работая с массивом размераn (см. ниже), но требования к пространству могут быть нежелательны для большихn, Есть ли алгоритм, который требует меньше места, особенно когда толькоiэлемент нужен?

Алгоритм, который строитkая перестановка последовательности0..n-1 со временема также космическая сложность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

Источник:http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf