Prevent memory error in itertools.permutation

python itertools
user506710 picture user506710 · Jun 28, 2011 · Viewed 8.9k times · Source

Firstly I would like to mention that i have a 3 gb ram.

I am working on an algorithm that is exponential in time on the nodes so for it I have in the code 

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

which generates all the combinations of vertices in a list and then i can work on one of the permutation.

However when i run the program for 40 vertices , it gives a memory error.

Is there any simpler way in implementation via which i can generate all the combinations of the vertices and not have this error.

Answer

Cédric Julien picture Cédric Julien · Jun 28, 2011

Try to use the iterator generated by the permutations instead of recreating a list with it : 

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

for item in perm_iterator:
   do_the_stuff(item)

by doing this, python will keep in memory only the currently used permutation, not all the permutations (in term of memory usage, it is really better ;) )

On the other side, once the memory problem solved, the time to treat all the permutations will be growing exponentially with the number of vertices....

Related questions

How do I use itertools.groupby()?

I haven't been able to find an understandable explanation of how to actually use Python's itertools.groupby() function. What I'm trying to do is this: Take a list - in this case, the children of an objectified lxml element Divide …

Read More
Permutations between two lists

I’m having trouble wrapping my head around a algorithm I’m try to implement. I have two lists and want to take particular combinations from the two lists. Here’s an example. names = 'a', 'b' numbers = 1, 2 the output in …

Read More
importing izip from itertools module gives NameError in Python 3.x

I am trying to import the izip module like so: from itertools import izip However after recently changing over from Python 2.7 to 3 - it doesn't seem to work. I am trying to write to a csv file: writer.writerows(izip(…

Read More