Пожалуйста, как я могу получить все эти двоичные перестановки, но без повторения в 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)
...
Было бы здорово, если бы это было примерно эффективно, так как мне придется сделать это со списком из 30 таких элементов.
Как сказал @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]
Здесь алгоритм из принятого ответа на вопрос об общем алгоритме, адаптированный к 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]
Что приятно в этом алгоритме, так это то, что вы можете возобновить его в любой момент. Если вы найдете способ расчета хороших отправных точек, можно также распараллелить. И цифры должны быть более компактными, чем списки, поэтому вы можете использовать их, если это возможно.
То, что вы пытаетесь сделать, - выбрать две позиции, в которых элемент будет равен 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}']
Рекурсивное решение:
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))