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

Here is a recursive solution:

def bin_combs_iter(ones, zeros):
    if not zeros:
        yield [1] * ones
    elif not ones:
        yield [0] * zeros
    else:
        for x in bin_combs_iter(ones - 1, zeros):
            x.append(1)
            yield x
        for x in bin_combs_iter(ones, zeros - 1):
            x.append(0)
            yield x


def bin_combs(ones, zeros):
    return list(bin_combs_iter(ones, zeros))

Answer 2

What you are trying to do is choose two positions at which the element will be 1.

Code

from itertools import combinations

def bit_patterns(size, ones):
    for pos in map(set, combinations(range(size), ones)):
        yield [int(i in pos) for i in range(size)]

Output

>>> print(*bit_patterns(4, 2), sep='\n')
[1, 1, 0, 0]
[1, 0, 1, 0]
[1, 0, 0, 1]
[0, 1, 1, 0]
[0, 1, 0, 1]
[0, 0, 1, 1]

Alternative

A fun alternative is to see the desired output as the binary representations which have only two ones. We can use this definition to get the output you want.

from itertools import combinations

def bit_patterns(size, ones):
    for t in combinations([1 << i for i in range(size)], ones):
        yield [int(n) for n in f'{sum(t):0{size}b}']

Answer 3

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.

Answer 4

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]