非递归最有效的Big-O排列算法Python 3（非内置）

Question

嗨大家为了我的数据结构分配，我必须找到最有效的方法（大智慧）来计算对象列表的排列。

我在网上找到了递归的例子，但这似乎不是最有效的方式;我尝试了自己的代码，但后来我意识到，当我计算可能的排列数时，我实际上正在制作算法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)

OUTPUT：

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

如果不是7，我把8或9或10，那些是排列的数量（我不会显示时间因为它花了太长时间）：

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)