N выберите r возможностей как увеличение двоичных чисел
Я ищу функцию, которая вводит (n,r) и выводит все способы, с помощью которых мы можем выбрать r объектов из строки из n объектов. Более того, мне бы хотелось, чтобы этот список представлял собой возрастающую двоичную последовательность.
Например:
(5,2)
выведет: [00011,00101,00110,01001,01010,01100,10001,10010,10100,11000]
Я попытался сделать это, рассматривая крайнюю правую единицу и проверяя, может ли она «сдвинуться влево, не наткнувшись на другую единицу». Если не может, то перехожу к следующему 1 и проверяю то же самое. Если любую из единиц можно «переместить влево», каждая единица справа от нее будет «сброшена».
Хотя мой код не работал при попытке использовать этот метод.
@nocomment Это будут строки
Пожалуйста, отредактируйте вопрос соответствующим образом.
«Хотя мой код не работал при попытке использовать этот метод» — так и должно быть, метод звучит правильно. Но мы не можем отладить код, который вы не показываете.
Ответы 4
Желаемый порядок — это просто лексикографический порядок, создаваемый itertools.combinations при выборе n – r позиций для 0 из n позиций:
from itertools import combinations
def binary_combinations(n, r):
for c in map(set, combinations(range(n), n - r)):
yield ''.join('0' if i in c else '1' for i in range(n))
print(*binary_combinations(5, 2), sep='\n')
Это выводит:
00011
00101
00110
01001
01010
01100
10001
10010
10100
11000
Демо здесь
Как мне вывести это в виде списка? Извините, я не знаком с словом «доходность».
print(list(binary_combinations(5, 2)))Может оказаться полезной функция комбинаций из библиотеки itertools. Вот моя попытка:
from itertools import combinations
def get_binary_strings(n, r):
res = []
for comb in combinations(list(range(n)), r):
num_decimal = sum(2**pos for pos in comb)
num_binary = bin(num_decimal).replace("0b", "")
res.append(str(num_binary))
res.sort(key=lambda n: int(n, 2))
res = ['0'*(n-len(s))+s for s in res]
return res
for s in get_binary_strings(5, 2):
print(s)
Начните с единиц, затем вставьте 0, но только после последнего 0:
def binary_combinations(n, r):
combs = ['1' * r]
while r < n:
r += 1
combs = [
c[:i] + '0' + c[i:]
for c in combs
for i in range(c.rfind('0') + 1, r)
]
return combs
print(binary_combinations(5, 2))
Вдохновленный мультипликативной формулой (как получить следующий combs из текущего) и
ответ Блхсинга (за размышление о том, как поставить 0 вместо 1).
Рекурсивная версия, может быть, более понятная:
def binary_combinations(n, r):
if r == n:
yield '1' * n
return
for comb in binary_combinations(n-1, r):
for i in range(comb.rfind('0') + 1, n):
yield comb[:i] + '0' + comb[i:]
print(list(binary_combinations(5, 2)))
Реализация вашего вопроса «перевернуть самый правый-01 и сбросить все остальное»:
def binary_combinations(n, r):
comb = '0' * (n-r) + '1' * r
while True:
yield comb
a, b, c = comb.rpartition('01')
if not b:
return
comb = a + '10' + c[::-1]
print(list(binary_combinations(5, 2)))
Что вы подразумеваете под «двоичной последовательностью» и «выводом»? Ваш
[00011,00101,00110,01001,01010,01100,10001,10010,10100,11000]недействителен для Python, это синтаксическая ошибка.