Generate unique binary permutations in python

Question

Please, how can I get all these binary permutations, but without repetition in Python?

 a = list(itertools.permutations([1, 1, 0, 0]))
 for i in range(len(a)):
     print a[i]

    (1, 1, 0, 0)
    (1, 1, 0, 0)
    (1, 0, 1, 0)
    ...

It would be great if it would be roughly efficient since I'll have to do that with a list of even 30 elements like this.

Answer 1

As @Antti said in a comment, this is equivalent to looking for combinations of positions of the input list which determine which bits in the output are 1.

from itertools import combinations

def binary_permutations(lst):
    for comb in combinations(range(len(lst)), lst.count(1)):
        result = [0] * len(lst)
        for i in comb:
            result[i] = 1
        yield result

for perm in binary_permutations([1, 1, 0, 0]):
    print(perm)

Output:

[1, 1, 0, 0]
[1, 0, 1, 0]
[1, 0, 0, 1]
[0, 1, 1, 0]
[0, 1, 0, 1]
[0, 0, 1, 1]

Answer 2

Here's the algorithm from the accepted answer to the generic algorithm question, adapted into Python 3 (should work in Python 2.7+). The function generate(start, n_bits) will generate all n-bit integers starting from start lexicographically.

def generate(start, n_bits):
    # no ones to permute...
    if start == 0:
        yield 0
        return

    # fastest count of 1s in the input value!!
    n_ones = bin(start).count('1')

    # the minimum value to wrap to when maxv is reached;
    # all ones in LSB positions
    minv = 2 ** n_ones - 1

    # this one is just min value shifted left by number of zeroes
    maxv = minv << (n_bits - n_ones)

    # initialize the iteration value
    v = start

    while True:
        yield v

        # the bit permutation doesn't wrap after maxv by itself, so,
        if v == maxv:
            v = minv

        else:
            t = ((v | ((v - 1))) + 1)
            v = t | (((((t & -t)) // ((v & -v))) >> 1) - 1)

        # full circle yet?
        if v == start:
            break

for i in generate(12, 4):
    print('{:04b}'.format(i))

Prints

1100
0011
0101
0110
1001
1010

If list output is generated, this can then be decorated:

def generate_list(start):
    n_bits = len(start)
    start_int = int(''.join(map(str, start)), 2)

    # old and new-style formatting in one
    binarifier = ('{:0%db}' % n_bits).format

    for i in generate(start_int, n_bits): 
        yield [int(j) for j in binarifier(i)]

for i in generate_list([1, 1, 0, 0]):
    print(i)

prints

[1, 1, 0, 0]
[0, 0, 1, 1]
[0, 1, 0, 1]
[0, 1, 1, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]

What is nice about this algorithm is that you can resume it at any point. If you find a way to calculate good starting points, it is possible to parallelize too. And the numbers should be more compact than lists, so you could use them if possible.