Создание уникальных бинарных перестановок в python

Ответ 1

Как сказал @Antti в комментарии, это эквивалентно поиску combinations позиций входного списка, которые определяют, какие биты на выходе равны 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)

Выход:

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

Ответ 2

Здесь алгоритм из принятого ответа на вопрос об общем алгоритме, адаптированный к Python 3 (должен работать в Python 2. 7+). Функция generate(start, n_bits) будет генерировать все n-битовые целые числа, начиная с start лексикографически.

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

Печать

1100
0011
0101
0110
1001
1010

Если создается вывод списка, это можно затем украсить:

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)

печать

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

Что приятно в этом алгоритме, так это то, что вы можете возобновить его в любой момент. Если вы найдете способ расчета хороших отправных точек, можно также распараллелить. И цифры должны быть более компактными, чем списки, поэтому вы можете использовать их, если это возможно.

Ответ 3

То, что вы пытаетесь сделать, - выбрать две позиции, в которых элемент будет равен 1.

Код

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

Выход

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

альтернатива

Веселой альтернативой является просмотр желаемого результата в виде двоичных представлений, которые имеют только два. Мы можем использовать это определение для получения требуемого результата.

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

Ответ 4

Рекурсивное решение:

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