第i k个排列的元件 [英] i-th element of k-th permutation

问题描述

的排列的任何命令，可以被选择，它并没有被辞书。有迹象表明，构建 K -th排列在算法为O（n）（见下文）。但这里的完整的排列是不需要的，只是它的我个元素。是否有算法，可以做的比 O（N）？

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)?

有通过工作大小的数组构造 K -th置换算法 N （见下文），但空间要求可能是不可取的大 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?

算法，构建 K 顺序 0到n-1 与时间-th排列和的空间复杂度 O（N）：

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

来源： http://webhome.cs.uvic.ca /~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

推荐答案

您可能不能得到第i个位数n个元素的O（n）的时间或空间的k个排列的，因为再presenting K的数量本身需要O（日志（N！））=为O（n log n）的位，并与它的任何操作都有相应的时间复杂度。

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.

这篇关于第i k个排列的元件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！