Предотвратить ошибку памяти в itertools.permutation

Question

Во-первых, я хотел бы отметить, что у меня есть оперативная память 3 ГБ.

Я работаю над алгоритмом, который экспоненциально по времени на узлах, поэтому для него у меня есть код

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

, который генерирует все комбинации вершин в списке, а затем яможет работать на одной из перестановок.

Однако, когда я запускаю программу для 40 вершин, она выдает ошибку памяти.

Есть ли более простой способ реализации, с помощью которого я могу сгенерировать всекомбинации вершин и не имеют этой ошибки.

Answer 1

Попробуйте использовать итератор, сгенерированный перестановками, вместо воссоздания списка с ним:

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

for item in perm_iterator:
   do_the_stuff(item)

делая это, python будет хранить в памяти только используемую в настоящее время перестановку, а не все перестановки (с точки зрения использования памяти это действительно лучше;))

С другой стороны, как только проблема с памятью будет решена, время обработки всех перестановок будет экспоненциально расти с числом вершин ....

Answer 2

Это не сработает.Цикл по итератору также не будет работать.Видите ли, если выполнение кода в цикле for занимает 1 микросекунду, полное выполнение займет 2,587 × 10 ^ 34 года.(См. http://www.wolframalpha.com/input/?i=40%21+microseconds+in+years)