第 k 个排列中的第 i 个元素。

Question

有没有一种快速算法来计算序列0..n-1的第i个元素（0≤i

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

这篇文章介绍了一种用于计算排列的新算法，称为Rank-Permutation算法。该算法通过使用递归和字典序等方面的优化，可以更快地计算出较大的排列。

- Yurim

---

您在http://cs.stackexchange.com或http://cstheory.stackexchange.com上提出此问题，可能会更容易得到一个好的答案。 - jkff

Answer 1

jkff所说的没错。你可以修改像你发布的那个算法，仅返回第k个排列的第i个元素，但你不会节省多少时间（或空间），并且肯定不会减少基本算法的大O复杂度。

你发布的无序排列代码不太适合修改，因为它必须循环遍历所有元素执行交换，而确定是否能够早期跳出循环非常痛苦。

然而，有一个类似的算法可以产生有序排列，并且可能会提前跳出该算法，但你仍需要执行i个内部循环才能得到第k个排列的第i个元素。

我已经将此算法实现为一个类，只是为了使其使用的各种常量整洁。下面的代码生成完整的排列，但应该很容易修改以仅返回第i个元素。

#!/usr/bin/env python

''' Ordered permutations using factorial base counting 

    Written by PM 2Ring 2015.02.15
    Derived from C code written 2003.02.13
'''

from math import factorial

class Permuter(object):
    ''' A class for making ordered permutations, one by one '''
    def __init__(self, seq):
        self.seq = list(seq)
        self.size = len(seq)
        self.base = factorial(self.size - 1)
        self.fac = self.size * self.base

    def perm(self, k):
        ''' Build kth ordered permutation of seq '''
        seq = self.seq[:]
        p = []
        base = self.base
        for j in xrange(self.size - 1, 0, -1):
            q, k = divmod(k, base)
            p.append(seq.pop(q))
            base //= j
        p.append(seq[0])
        return p


def test(seq):
    permuter = Permuter(seq)
    for k in xrange(permuter.fac):
        print '%2d: %s' % (k, ''.join(permuter.perm(k)))


if __name__ == '__main__':
    test('abcd')

这个算法比无序置换生成器的开销更大：它需要提前计算阶乘，当然阶乘会非常快地变得很大。而且，每个内部循环还需要一个额外的除法。因此，一旦找到第i个元素，通过跳出内部循环节省时间可能会被这些开销抵消。

顺便说一下，你问题中的代码还有改进空间。特别是，k /= n 应该写成 k //= n 以确保使用整数除法；你的代码在Python 2上运行良好，但在Python 3上不行。然而，由于我们需要商和余数，使用内置的 divmod() 函数是有意义的。另外，通过重新组织一些东西，我们可以避免多次计算 n - 1。

#!/usr/bin/env python

def kth_permutation(n, k):
    p = range(n)
    while n:
        k, j = divmod(k, n)
        n -= 1
        p[n], p[j] = p[j], p[n]
    return p

def test(n):
    last = range(n)
    k = 0
    while True:
        p = kth_permutation(n, k)
        print k, p
        if p == last:
            break
        k += 1

test(3)

输出

0 [1, 2, 0]
1 [2, 0, 1]
2 [1, 0, 2]
3 [2, 1, 0]
4 [0, 2, 1]
5 [0, 1, 2]

- PM 2Ring

Answer 2

您可能无法在O(n)时间或空间内获取n个元素的第k个排列的第i位数字，因为表示数字k本身需要O(log(n!)) = O(n log n)位，任何与之相关的操作都具有相应的时间复杂度。

- jkff

---

这是一个很好的观点，我没有考虑到k的比特复杂度。对于大量的n来说，这可能比在数组中存储排列更成问题。 - Yurim

我对这个答案感到困惑。OP明确指出了一种时间和空间复杂度为O(n)的算法。也许表示数字k本身需要n log n位，但我认为通常我们不会将数字表示视为算法的问题（尽管从理论上讲我们会考虑）。 - justhalf

那就是问题所在——你既不能同时担心渐近行为（当n足够大时的行为），又无视表示k需要nlogn比特的事实。 - jkff