第 k 个排列的第 i 个元素
i-th element of k-th permutation
是否有快速算法来计算序列 0..n-1 的第 k 个排列 (0 <= k < n!) 的第 i 个元素 (0 <= i < n)？
可以选择排列的任何顺序，不必按字典顺序排列。有一些算法可以在 O(n) 中构造第 k 个排列（见下文）。但是这里不需要完整的排列，只需要第 i 个元素。有没有比 O(n) 做得更好的算法？
是否有一种算法的 space 复杂度小于 O(n)？
有些算法通过处理大小为 n 的数组来构建第 k 个排列（见下文），但是 space 要求对于大型 n。有没有需要更少 space 的算法，尤其是当只需要第 i 个元素时？
构造序列0..n-1第k次排列的算法，时间和space复杂度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
您可能无法在 O(n) 时间或 space 内获得 n 元素的第 k 个排列的第 i 个数字，因为表示数字 k 本身需要 O(log(n!) ) = O(n log n)位，对其进行任何操作都有相应的时间复杂度。
jkff 说的。您可以修改一个算法，就像您发布到 return 第 k 个排列的第 i 个元素的算法，但您不会节省太多时间（或 space），而且您肯定会赢'降低基本算法的Big-O复杂度。
您发布的无序排列代码实际上并不适合修改，因为它必须遍历执行其交换的所有元素，并且很难确定是否有可能提前跳出循环。
然而，有一个类似的算法可以产生有序的排列，并且可以提前突破那个算法，但是你仍然需要执行 i 内循环来得到第 i 个元素第 k 个排列。
我已经将这个算法实现为 class，只是为了保持它使用的各种常量整洁。下面的代码产生完整的排列，但应该很容易修改为 return 第 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 个元素，跳出内部循环所节省的时间可能会被这些开销所抵消。
FWIW，您问题中的代码还有改进的余地。特别是，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]
是否有快速算法来计算序列 0..n-1 的第 k 个排列 (0 <= k < n!) 的第 i 个元素 (0 <= i < n)？
可以选择排列的任何顺序，不必按字典顺序排列。有一些算法可以在 O(n) 中构造第 k 个排列（见下文）。但是这里不需要完整的排列，只需要第 i 个元素。有没有比 O(n) 做得更好的算法？
是否有一种算法的 space 复杂度小于 O(n)？
有些算法通过处理大小为 n 的数组来构建第 k 个排列（见下文），但是 space 要求对于大型 n。有没有需要更少 space 的算法，尤其是当只需要第 i 个元素时？
构造序列0..n-1第k次排列的算法，时间和space复杂度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
您可能无法在 O(n) 时间或 space 内获得 n 元素的第 k 个排列的第 i 个数字，因为表示数字 k 本身需要 O(log(n!) ) = O(n log n)位，对其进行任何操作都有相应的时间复杂度。
jkff 说的。您可以修改一个算法，就像您发布到 return 第 k 个排列的第 i 个元素的算法，但您不会节省太多时间（或 space），而且您肯定会赢'降低基本算法的Big-O复杂度。
您发布的无序排列代码实际上并不适合修改，因为它必须遍历执行其交换的所有元素，并且很难确定是否有可能提前跳出循环。
然而，有一个类似的算法可以产生有序的排列，并且可以提前突破那个算法，但是你仍然需要执行 i 内循环来得到第 i 个元素第 k 个排列。
我已经将这个算法实现为 class，只是为了保持它使用的各种常量整洁。下面的代码产生完整的排列，但应该很容易修改为 return 第 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 个元素，跳出内部循环所节省的时间可能会被这些开销所抵消。
FWIW，您问题中的代码还有改进的余地。特别是，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]