非递归最有效的 Big-O 置换算法 Python3（非内置）

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)

输出：

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 生成器函数，这样您将始终只生成您需要的数量，而不是预先计算它们并将它们存储在内存中。如果你想要一个这样的例子，我可以给你一个。

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

编辑：

这是我承诺的堆算法的 python 实现 (https://en.wikipedia.org/wiki/Heap%27s_algorithm)生成N！排列，其中每个排列的生成都需要分摊 O(1) 时间，并且使用 O(n) space 复杂度（通过 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)

非递归最有效的 Big-O 置换算法 Python3（非内置）

Non-recursive Most Efficient Big-O Permutation Alghoritm Python3 (non-built-in)

big-o

permutation

memory-efficient

python-3.x