Проходя все двоичные комбинации с некоторыми числами как "?"

Question

Мне нужно сгенерировать все возможные двоичные представления данной строки, где некоторые символы "?" и другие 1 или 0.

Я пытаюсь выполнить рекурсивный поиск, но у меня возникают странные проблемы, которые я не могу понять.

userInput = list(input())
anslist = []
def fill(inp):
    #print(inp)
    if inp.count("?") == 0:
        print(inp, "WAS ADDED")
        anslist.append(inp)
        return


    for a in range(0, len(userInput)):
        if inp[a] == "?":
            inp[a] = 1
            fill(inp)
            inp[a] = 0
            fill(inp)
            return
print(anslist)   

Для ввода? 01? 1 я должен получить: 00101, 00111, 10101 и 10111 но я получаю 10111 10101 00101 распечатан. Кроме того, список не работает должным образом. Я просто не могу понять это.

Answer 1

a list - это тип mutable , это означает, что у вас есть только список one , в который внесены все изменения. Это заставляет ваш первый вызов fill(inp) также заполнить оставшиеся «?» в inp, таким образом, давая вам только один результат со вторым вариантом для первого? (первый? = 1: два результата, первый? = 0: один результат, потому что последний результат первого? все еще сохраняется в списке)

Чтобы решить эту проблему, используйте list.copy(). Это передаст копию списка в fill() и, таким образом, оставит исходный список таким, какой он есть.

Ваш полный код с .copy() и другими незначительными изменениями:

anslist = []
def fill(inp):
    if inp.count("?") == 0:
        print(inp, "WAS ADDED")
        anslist.append(inp)
        return

    for a in range(len(inp)):  # range(0, x) is equivalent to range(x); try to limit global variables
        if inp[a] == "?":
            inp[a] = 1
            fill(inp.copy())  # list is mutable
            inp[a] = 0
            fill(inp.copy())  # see above
            return
user_input = list(input())
fill(user_input)
print(anslist)

Answer 2

Простое решение, которое позволяет избежать использования глобальных или библиотеки:

def fill(digits):

    if not digits:
        return []

    first, *rest = digits

    strings = fill(rest) if rest else ['']

    if first == '?':
        return ['0' + string for string in strings] + ['1' + string for string in strings]

    return [first + string for string in strings]

userInput = input()

print(fill(userInput))

Пытается прописать , а не выполнять самые эффективные операции с массивами, что оставлено в качестве упражнения для ОП.

OUTPUT

> python3 test.py
?01?1
['00101', '00111', '10101', '10111']
> python3 test.py
???
['000', '001', '010', '011', '100', '101', '110', '111']
> python3 test.py
?
['0', '1']
> python3 test.py

[]
>

Answer 3

Вот пример решения без использования встроенных инструментов. Здесь мы используем рекурсию, когда мы встречаемся? во время перебора нашего ввода мы заменяем его на '0' и '1' и добавляем результат fill() того, что следует после текущего индекса.

userInput = input()

def fill(inp):
    ret = []
    for idx, i in enumerate(inp):
        if i == '?':
            for rest in fill(inp[idx+1:]):
                ret.append(inp[:idx] + '0' + rest)
                ret.append(inp[:idx] + '1' + rest)
            break
    else:
        return [inp]
    return ret

print(fill(userInput))

выход

?01?1 -> ['00101', '10101', '00111', '10111']
???   -> ['000', '100', '010', '110', '001', '101', '011', '111']

Answer 4

import itertools
import re

inp = "?01?1"
for combination in itertools.product("01", repeat=inp.count("?")):
    i_combination = iter(combination)
    print(re.sub("\?",lambda m: next(i_combination),inp))

это просто использует встроенный itertools.product для создания всех возможных строк "01" длины N (однако в строке есть много вопросительных знаков)

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

затем мы используем re.sub, чтобы заменить наши продукты на наши оригинальные строки вместо наших вопросительных знаков

вот оно в реплее https://repl.it/@JoranBeasley/AssuredAncientOpengroup

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

если вы не хотите использовать встроенный itertools.product ... Просто напишите свой собственный

def my_product(s,r):
  if r < 1:
    yield ""
  for i in range(r):
    for c in s:
      for partial in  my_product(s,r-1):
        yield c+partial

то же самое со встроенным iter

def my_iter(s):
    for c in s:
        yield c

и, наконец, нам нужно написать собственный настраиваемый subber

def my_substitute(s,replacement):
    iter_replacement = my_iter(replacement)
    while s.count("?"):
         s = s.replace("?",next(iter_replacement))
    return s

теперь мы связываем все это вместе таким же образом

inp = "?01?1"
for combination in my_product("01", inp.count("?")):
    print(my_substitute(inp,combination))

Answer 5

Пример кода Python с использованием itertools.product (вы можете использовать эквивалентную реализацию, но это нормально)

from itertools import product

def generate_combinations(inp):
   count = 0 
   for a in range(0, len(inp)):
      if inp[a] == "?": count += 1
   combinations = []
   for comb in product(range(2), repeat=count):
      pos = 0
      cinp = inp[:]
      for a in range(len(cinp)):
         if cinp[a] == '?':
           cinp[a] = str(comb[pos])
           pos += 1
       combinations.append(cinp)
    return combinations

пример использования:

print(generate_combinations('?01?1'))