Find unique permutation of a list binary values without generating all possibilities

Question

Forgive my ignorance. I have a brain fart at the moment and unable to come up with a solution. Let's say I have a list of [1, 1, 0, 0]. I want to calculate all the four digits binary numbers that have exactly two 1s and two zeros, like:

['0110', '0011', '0101', '1100', '1010', '1001']

This works:

from itertools import permutations

set([''.join(x) for x in list(permutations('0011', 4))])

But this calculate the entire permutations and then discards the duplicate. Meaning, it calculates 24 times but I only need 6. It is much more significant if the collection is [1, 1, 1, 1, 0, 0, 0, 0].

This should be very easy but I just can't wrap my head around it.

[doc](https://docs.python.org/2/library/itertools.html#itertools.permutations) explicitly says that elements are treated unique based on position and not value. So you using `permutations()` is doesn't seem to be an option. — gaganso, Jun 02 '16 at 04:50
@SilentMonk, that's why I asked. permutation is not useful here. — Sam R., Jun 02 '16 at 04:51
@Kasravand: This is a different (much simpler) problem than the one you linked as duplicate, so the answer presented there is overkill for this case. — Tim Pietzcker, Jun 02 '16 at 05:19
^ agree with Tim. The marked duplicate allows for arbitrary integers in the original set. This question only has 1's and 0's. To create better google-ability I suggest reflecting the specificity of this question better in the title to reflect the difference. — D Adams, Jun 02 '16 at 05:30

score 5 · Accepted Answer · answered Jun 02 '16 at 05:17

5

Use itertools.combinations() to find all possible positions for your ones, then construct the numbers using those positions:

def binary(length=4, ones=2):
    result = []
    for positions in combinations(range(length), ones):
        result.append("".join("1" if _ in positions else "0" for _ in range(length)))
    return result

Result:

In [9]: binary()
Out[9]: ['1100', '1010', '1001', '0110', '0101', '0011']

In [10]: binary(5)
Out[10]:
['11000', '10100', '10010', '10001', '01100', '01010', '01001', '00110', '00101', '00011']

In [11]: binary(4,1)
Out[11]: ['1000', '0100', '0010', '0001']

In [12]: binary(4,4)
Out[12]: ['1111']

answered Jun 02 '16 at 05:17

Tim Pietzcker

313,408
56
485
544

This is a fantastic answer -> didn't see it on the duplicate question – D Adams Jun 02 '16 at 05:25
WOW. MAN! nailed it. Some people are just smart. Thanks a lot. – Sam R. Jun 02 '16 at 05:26
I suspect this approach could be extended to tackle the more general problem. Somehow there is a concise statement to be made about this being a combinatorics problem. – D Adams Jun 02 '16 at 05:37

namit · Answer 2 · 2016-06-02T07:30:22.263

This post is bit late.
@Tim Pietzcker 's answer is excellent, but one inner loop inside append is very hard for me to digest;

so i write same in simple way and its around 4-7 times faster.

def binary(length=4, ones=2):
    result = []
    rr = ['0'] * length  ## initialize empty list with ZEROS of given length
    for c in itertools.combinations(range(length), ones):
        r = rr[:] ## create a copy of initialized list
        for x in c:
            r[x] = '1' ## Change ZERO to ONE based on different combinations of positions 
        result.append("".join(r))
    return result

Find unique permutation of a list binary values without generating all possibilities

2 Answers2