非递归最高效的 Big-O 排列 Alghoritm Python3(非内置)

Question

嗨，伙计们 对于我的数据结构作业，我必须找到最有效的方法(big-o wise)来计算对象列表的排列。

我在网络上找到了递归示例，但这似乎不是最有效的方法;我尝试了自己的代码，但后来我意识到，当我计算可能的排列数量时，我实际上是在使我的算法成为O(！n)。有什么建议吗？

from random import sample
import time
start = time.time()
testList = list(x for x in range(7))
print('list lenght: %i objects' % len(testList))
nOfPerms = 1
for i in range(1,len(testList)+1):
nOfPerms *= i
print('number of permutations:', nOfPerms)
listOfPerms = []
n = 1
while n <= nOfPerms:
perm = tuple(sample(testList, len(testList)))
listOfPerms.append(perm)
permutations = set(listOfPerms)
if len(permutations) == len(listOfPerms):
n += 1
else:
del(listOfPerms[-1])
end = time.time() - start
print('time elapsed:', end)

输出：

list lenght: 7 objects
number of permutations: 5040
time elapsed: 13.142292976379395

如果我放 8 或 9 或 10 而不是 7，这些是排列的数量(我不会显示时间，因为它花费的时间太长)：

list lenght: 8 objects
number of permutations: 40320
list lenght: 9 objects
number of permutations: 362880
list lenght: 10 objects
number of permutations: 3628800

Answer 1

我相信这将是你能做的最好的事情。 生成列表的排列数会生成 n！ 排列。由于您需要生成它们，因此这也是需要多少时间(O(n！您可以尝试做的是使其成为python生成器函数，这样您将始终仅生成所需的数量，而不是预先计算它们并将它们存储在内存中。如果你想要一个例子，我可以给你一个。

对不起，这可能是一个非常负面的答案。这是一个很好的问题，但我很确定这是你能做的最好的，渐近。您可以稍微优化代码本身以使用更少的指令，但最终这不会有太大帮助。

编辑：

这是我承诺的Heap算法的python实现 (https://en.wikipedia.org/wiki/Heap%27s_algorithm) 生成 N！排列，其中每个排列的生成需要摊销的 O(1) 时间，并且使用 O(n) 空间复杂度(通过 alteri

def permute(lst, k=None):
if k == None:
k = len(lst)
if k == 1:
yield lst
else:
yield from permute(lst, k-1)
for i in range(k-1):
if i % 2 == 0:
#even
lst[i], lst[k-1] = lst[k-1], lst[i]
else:
#odd
lst[0], lst[k-1] = lst[k-1], lst[0]
yield from permute(lst, k-1)

for i in permute([1, 2, 3, 4]):
print(i)