计数算法

您可以使用以下生成器函数:

from itertools import product  # or use `product` function from below

def states(s):
    for tpl in product("01", repeat=s.count("?")):
        gaps = iter(tpl)  # iterator over the product tuple 
        yield "".join(next(gaps) if c == "?" else c for c in s)

list(states("1?01?1"))
# ['100101', '100111', '110101', '110111']
list(states("???"))
# ['000', '001', '010', '011', '100', '101', '110', '111']
list(states("11?"))
# ['110', '111']
list(states("11"))
# ['11']

你形成了的笛卡尔乘积 "01" x "01" x ... x "01" 因为有多少缺口。然后你用产品的元组重复地填补空白。

你可以自己写 product 如果不允许使用库,则可作为替换插件:

def product(pool, repeat=1):
    if not repeat:
        yield []
    else:
        for elmnt in pool:
            for tpl in product(pool, repeat-1):
                yield [elmnt] + tpl

还有另一个实现 产品 在 itertools.product docs 。

一次扩展一个字符:

s = '1?01?1'

ss = ['']
for c in s:
    if c == '?':
        c = '01'
    ss = [s + d for s in ss for d in c]

for s in ss:
    print(s)

输出( Try it online! )以下为:

100101
100111
110101
110111

您可以使用递归方法来解决这个问题。下面是Python中的一个算法,它为给定的字符串生成所有可能的状态:

1. 定义一个递归函数,让我们称之为generate_states,它采用当前状态、剩余字符串和一个列表来存储生成的状态。
2. 如果剩下的字符串为空,请将当前状态附加到生成的状态列表中并返回。
3. 否则,请检查剩余字符串的第一个字符: --如果这是一个问号,那么进行两次递归调用以生成状态,其中当前状态附加0和1,其余字符串不包含第一个字符。 --如果不是问号,则递归调用generate_states,将当前状态附加第一个字符,并将剩余的字符串不包含第一个字符。
4. 实现一个助手函数,让我们称之为count_states,它为生成的状态初始化一个空列表,并使用空的当前状态、输入字符串和存储状态的列表来调用generate_states。
5. 最后,返回生成的状态列表。 以下是该算法的Python实现:

def generate_states(current_state、remaining_string、states): 如果不是remaining_string: states.append(当前状态) 回来

  if remaining_string[0] == '?':
      generate_states(current_state + '0', remaining_string[1:], states)
      generate_states(current_state + '1', remaining_string[1:], states)
  else:
      generate_states(current_state + remaining_string[0], remaining_string[1:], states)


  def count_states(input_string):
      states = []
      generate_states('', input_string, states)
      return states


  input_string = '1?01?1'
  possible_states = count_states(input_string)
  for state in possible_states:
      print(state)