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
– ShadowRanger, Commented Jan 14, 2016 at 3: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
– Jeff Mercado, Commented Jan 14, 2016 at 3:27
Possible duplicate of Generate permutations of list with repeated elements — ShadowRanger
– ShadowRanger, Commented Jan 14, 2016 at 3: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 — tpup1
– tpup1, Commented Jan 15, 2016 at 4:59

Community · Accepted Answer · 2017-05-23 12:23:28Z

2

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.

edited May 23, 2017 at 12:23

CommunityBot

11 silver badge

answered Jan 14, 2016 at 4:18

DSM

355k67 gold badges606 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

tpup1 Over a year ago

Thanks heaps! I really appreciate it

MadhaviJ · Accepted Answer · 2016-01-14 05:01:10Z

1

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

answered Jan 14, 2016 at 5:01

MadhaviJ

2,3555 gold badges27 silver badges40 bronze badges

1 Comment

DSM Over a year ago

That's what the OP is already doing, right in the code, and explains why it doesn't work well for this use case.

Collectives™ on Stack Overflow

How to get permutations in Python with no repeated cases

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related