How to get permutations in Python with no repeated cases

Question

I'm doing some work with the Ising model. I've written a code to help me count the multiplicity of a lattice but I can't get up to any big numbers without getting a MemoryError.

The basic idea is, you have a list of zeros and ones, say [0,0,1,1]. I want to generate a set of all possible orderings of the ones and zeros. So in this example I want a set like this:

[(1,1,0,0),(1,0,1,0),(1,0,0,1),(0,1,1,0),(0,1,0,1),(0,0,1,1)]

At the moment I have done it like this:

set_initial=[0,0,1,1]
set_intermediate=[]
for subset in itertools.permutations(set_initial,4):
    set_intermediate.append(subset)
set_final=list(set(set_intermediate))

The issue is that in the set_intermediate, for this example, there are 2^4 elements, only six of which are unique. And to take another example such as [0,0,0,0,0,0,0,0,1], there are 2^9 elements, only 9 of which are unique.

Is there another way of doing this so that set_intermediate isn't such a bottleneck?

Well, at the most basic level, you could avoid storing the duplicates by using a `set` as your temporary storage in the first place. `set_intermediate = set()`, `set_intermediate.add(subset)`, then convert to `list` at the end. Duplicates eliminated as they occur. — ShadowRanger, Jan 14 '16 at 03:27
Isn't it enough to just do `set(itertools.permutations(set_initial, 4))`? Permutations is a generator so if you just add the results to a list unconditionally, you'll get those repetitions. If you put it into a set immedieately, the repetitions wouldn't be added. — Jeff Mercado, Jan 14 '16 at 03:27
Possible duplicate of [Generate permutations of list with repeated elements](http://stackoverflow.com/questions/4250125/generate-permutations-of-list-with-repeated-elements) — ShadowRanger, Jan 14 '16 at 03:30
Thanks guys. I tried this too, it does work, but it's not very efficient so again only for smallish lists. I ended up finding a solution [here](http://stackoverflow.com/questions/6284396/permutations-with-unique-values) — tpup1, Jan 15 '16 at 04:59

score 2 · Answer 1 · edited May 23 '17 at 12:23

Instead of permutations, you can think in terms of selecting the positions of the 1s as combinations. (I knew I'd done something similar before..)

from itertools import combinations

def binary_perm(seq):
    n_on = sum(seq)
    for comb in combinations(range(len(seq)), n_on):
        out = [0]*len(seq)
        for loc in comb:
            out[loc] = 1
        yield out

Not super-speedy, but generates exactly the right number of outputs, and so can handle longer sequences:

>>> list(binary_perm([0,0,1,1]))
[[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1]]
>>> %timeit sum(1 for x in binary_perm([1]+[0]*10**4))
1 loops, best of 3: 409 ms per loop

Of course, usually you'd want to avoid looping over these in the first place, but depending on what you're doing with the permuations you might not be able to get away with simply calculating the number of unique permutations directly.

Thanks heaps! I really appreciate it – tpup1 Jan 15 '16 at 05:01 — tpup1, Jan 15 '16 at 05:01

score 1 · Answer 2 · answered Jan 14 '16 at 05:01

1

Try this inbuilt method itertools.permutation(iterable,r)

answered Jan 14 '16 at 05:01

Madhavi Jouhari

2,282
5
25
40

That's what the OP is already doing, right in the code, and explains why it doesn't work well for this use case. – DSM Jan 14 '16 at 05:26

How to get permutations in Python with no repeated cases

2 Answers2