Prevenir el error de memoria en itertools.permutation

Question

En primer lugar, me gustaría mencionar que tengo un 3 gb ram.

estoy trabajando en un algoritmo que es exponencial en el tiempo en los nodos de modo de que tengo en el código

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

que genera todas las combinaciones de los vértices en una lista y luego puedo trabajar en una de la permutación

Sin embargo, cuando ejecuto el programa para 40 vértices, se produce un error de memoria.

¿Hay alguna manera más simple en la implementación a través de la cual puedo generar todas las combinaciones de los vértices y no tener este error?

Answer 1

intenta utilizar el iterador generada por las permutaciones en lugar de volver a crear una lista con ella:

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

for item in perm_iterator: 
    do_the_stuff(item) 

al hacer esto, pitón guardará en la memoria solamente la permutación se utiliza actualmente, no todas las permutaciones (en términos del uso de la memoria, es realmente mejor;))

Por otro lado, una vez que el problema de memoria resuelto, el tiempo para el tratamiento de todas las permutaciones estará creciendo exponencialmente con el número de vértices ....

Answer 2

No funcionará Looping sobre un iterador tampoco funcionará. Verá, si el código en el ciclo for toma 1 microsegundo para ejecutarse, tomará 2.587 × 10^34 años para ejecutarse por completo. (Consulte http://www.wolframalpha.com/input/?i=40%21+microseconds+in+years)