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.

I.e. you're asking for "binary numbers of length N and exactly M bits set" — Antti Haapala -- Слава Україні, May 29 '18 at 20:47
https://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa — Antti Haapala -- Слава Україні, May 29 '18 at 20:52
The idea of permutations of values with duplicates is ambiguous about the discernibility of the duplicates. As [the docs](https://docs.python.org/3/library/itertools.html#itertools.permutations) explain, `itertools.permutations` chooses always discernible, because that's the hard one. Because the easy one—the one you want–is just… what @AnttiHaapala said. — abarnert, May 29 '18 at 20:53
Related: [permutations with unique values](//stackoverflow.com/q/6284396) — Aran-Fey, May 29 '18 at 21:07
@AnttiHaapala there _is_ a python solution and it looks very much like the most upvoted one here: https://stackoverflow.com/a/1851138/6451573. Sounds like a duplicate to me. — Jean-François Fabre, May 30 '18 at 06:01
@Jean-FrançoisFabre no it isn't, even though there is a Python solution, because *all* Python solutions cannot possibly go there. — Antti Haapala -- Слава Україні, May 30 '18 at 07:10
There cannot be discussion about the best *Python* solution and their trade-offs. — Antti Haapala -- Слава Україні, May 30 '18 at 07:12

score 13 · Answer 1 · answered May 29 '18 at 20:49

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]

It will be good not to take the MCVE too literally, for example, if the code can still do something sensible with an input like `[1, 1, 0, 0, 'potato']`. — wim, May 29 '18 at 20:56

Antti Haapala -- Слава Україні · Answer 2 · 2018-05-29T23:20:41.950

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

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.

This is fascinating and I'm glad you did it, but I'd feel uncomfortable using it as I have no idea why it works. The source doesn't explain why, so to some extent I'm just blindly trusting that it works. It would be nice to see it thoroughly tested against one of the other methods. A performance comparison would also help justify it. — Alex Hall, May 30 '18 at 09:27

Olivier Melançon · Answer 3 · 2018-05-30T12:50:47.217

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}']

@AlexHall it is simple: you just count the number of digits, generate powers of 2 up to N - 1; then count number of ones; change the **2** and 4 accordingly — Antti Haapala -- Слава Україні, May 29 '18 at 20:55

hilberts_drinking_problem · Answer 4 · 2018-05-30T20:07:42.413

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))

edited May 30 '18 at 20:07

answered May 29 '18 at 21:42

hilberts_drinking_problem

11,322
3
22
51

You need to call `bin_combs_iter` recursively, not `bin_combs`, or you'll use lots of memory for large inputs. – Alex Hall May 30 '18 at 17:43

Generate unique binary permutations in python

4 Answers4

Code

Output

Alternative