防止itertools.permutation中的内存错误

Question

首先，我想提一下我电脑的内存是3GB。

我正在做一个算法，这个算法在处理节点时的时间复杂度是指数级的，所以在我的代码里有

perm = list( itertools.permutations(list(graph.Nodes))) # graph.Nodes is a tuple of 1 , 2 , ... n integers

这段代码会生成一个列表，里面包含所有顶点的组合，然后我可以在这些组合中选择一个进行处理。

但是，当我运行程序处理40个顶点时，它出现了内存错误。

有没有什么更简单的方法可以实现，生成所有顶点的组合，而不会出现这个错误呢？

Answer 1

这段代码是行不通的。即使是用迭代器来循环也不行。你想想，如果这个循环里的代码每次运行需要1微秒，那么要完全运行完毕就需要2.587×10^34年！(你可以查看这个链接了解更多：http://www.wolframalpha.com/input/?i=40%21+microseconds+in+years)

Answer 2

试着使用由排列生成的迭代器，而不是重新创建一个列表：

perm_iterator = itertools.permutations(list(graph.Nodes))

for item in perm_iterator:
   do_the_stuff(item)

这样做的话，Python 只会在内存中保留当前正在使用的排列，而不是所有的排列（从内存使用的角度来看，这样真的更好 ;)）

另一方面，一旦解决了内存问题，处理所有排列所需的时间会随着顶点数量的增加而呈指数增长……