是否有一种快速算法来计算序列0..n-1 (0 <= i < n)的第k个排列(0 <= k < n!)的第i个元素？

可以选择排列的任何顺序，而不必按词典顺序排列。有一些算法可以构造第-
k个置换O(n)（请参见下文）。但是，这里不需要完整的排列，只需i第-个元素即可。有没有比这更好的算法O(n)？

是否有一种算法的空间复杂度小于O（n）？

有一些算法可以k通过处理大小数组来构造第n
个置换n（请参见下文），但是空间需求对于large可能是不希望的n。是否有一种算法需要较少的空间，尤其是仅i需要-th元素时？

算法构建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