Too many permutations in python

Question

My program needs to have all the combinations of 2s and 0s in a list of lists. Ex: [[0,0,0,2],[0,0,2,0],[0,2,0,0]....]. I will always have n^2 elements in each sub list where there are n-1 times 2s. So I should have n^2!/((n^2-n)!*(n-1)!) results.

The problem is my code first calculates all the permutations, then removes the duplicates. So for n = 4 there will be 16! sublists, which crashes my computer. How can I fix this? (it needs to handle at least n = 8)

Here is the code:

servers = n*n   #number of elements in each sublist
infected = n - 1 #number of 2s
grid = [ 0 for a in range(servers)] #list representing grid, with all 0s
grid = grid[:-infected] + infected * [2] #make last ones 2s

all_infections = list(itertools.permutations(grid))  # !!PROBLEM!! create all permutations of infection (touple)
all_infections = [list(a) for a in all_infections]   # Convert touple to lists


all_infections.sort()
all_infections = list(k for k,_ in itertools.groupby(all_infections)) #remove duplicates

combinations = len(all_infections)
print (all_infections)

results = []

for index in range(combinations): #calculate the infected states
    results = results + [grid_infecter(all_infections[index],n)]

Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [MCVE](http://stackoverflow.com/help/mcve) applies here. Your code does not execute on its own; we really like to be able to reproduce the problem, find a repair, and then test that repair. — Prune, Oct 22 '15 at 20:57
Also, let's make sure we understand the problem in general terms, rather than assignment terms. You have a 4x4 matrix with three 2's and the rest 0's. You need to consider all possible permutations of this arrangement. Is this correct? — Prune, Oct 22 '15 at 21:09

score 1 · Accepted Answer · answered Oct 22 '15 at 22:04

Your main problem is the combinatorial explosion far beyond the actual problem requirements. As you said, the n=8 case needs only 64!/(57! 7!) results. Why store them all at once?

This leaves you two basic choices:

Write your own permutation routine. These are easy enough to find with a basic search, such as this one.
Build a generator stream from permutations() and eliminate the duplicates before they ever get into your list.

Like so:

def no_duplicate(gen):
   previous = set()
   for permutation in gen:
      if permutation not in previous:
         previous.add(permutation)
         yield permutation

# Now set up a generator pipeline for the permutations
infection_stream = (no_duplicate(itertools.permutations(grid)))
result_stream = (grid_infecter(dish) for dish in infection_stream)

result_stream is a generator that you can use for whatever purpose you wish, such as:

results = [_ for _ in result_stream]

The magic of generators is that, so far, we have only one active permutation at any time. The unique ones are stored in that "previous" set in no_duplicates, but that's the only place you have a potential space problem. If that exceeds your computer's memory or your patience (after all the algorithm is O(n^2 !), then you'll need to write your own permutation generator so you can handle them one at a time without a long-term "remembering" device.

I searched farther down the list and found a single [posting](http://stackoverflow.com/questions/6534430/why-does-pythons-itertools-permutations-contain-duplicates-when-the-original) that encompasses all of the above, as well as what appears to be an improvement on my link in point 1 above. — Prune, Oct 22 '15 at 22:17

Too many permutations in python

1 Answers1