jkff所说的没错。你可以修改像你发布的那个算法,仅返回第k个排列的第i个元素,但你不会节省多少时间(或空间),并且肯定不会减少基本算法的大O复杂度。
你发布的无序排列代码不太适合修改,因为它必须循环遍历所有元素执行交换,而确定是否能够早期跳出循环非常痛苦。
然而,有一个类似的算法可以产生有序排列,并且可能会提前跳出该算法,但你仍需要执行i个内部循环才能得到第k个排列的第i个元素。
我已经将此算法实现为一个类,只是为了使其使用的各种常量整洁。下面的代码生成完整的排列,但应该很容易修改以仅返回第i个元素。
''' 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。
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]