使用一些数字作为“？”来遍历所有二进制组合。

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。此外，anslist 没有正常工作。我似乎无法弄清楚这个问题所在。

- Quiti

---

使用Python的itertools.product来生成所有1和0的组合，对于所有?的位置逐一分配到一个数组中，并推入anslist中。 - Nikos M.

如果您不想使用itertools.product，可以使用嵌套循环（对于固定数量的位置）或更一般的递归。 - Nikos M.

我不想使用内置工具。而且，我无法知道元素的数量（=循环的数量），因此递归是解决问题的方法。 - Quiti

@PatrickArtner 不，我在这里学习。 - Quiti

Answer 1

以下是不使用内置工具的示例解决方案。我们在迭代输入时使用递归，当遇到“？”时，我们将其替换为“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']

- Filip Młynarski

---

这很不错 :) - Joran Beasley

看到你的回答这么好，我想删除我的: D，但很高兴听到这个:) - Filip Młynarski

Answer 2

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来创建长度为N（字符串中有多少个问号）的所有"01"可能组合的字符串。

然后将每一个字符串转换成一个迭代器，在迭代过程中，每个项目都在被看到时被消耗掉。

接着我们使用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

与内置迭代器相同

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

最后，我们需要编写自己的自定义订阅器。

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

- Joran Beasley

Answer 3

一个避免使用全局变量或库的简单解决方案：

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

尝试将事物“拼凑”出来，而不是进行最有效的数组操作，这留给OP作为练习。

> 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

[]
>

- cdlane

Answer 4

一个列表是一种可变类型，这意味着您只有一个列表，所有修改都在其上进行。这导致您的第一个调用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)

- user24343

Answer 5

这是使用itertools.product的Python示例代码（您也可以使用等效实现，但这个很好）

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

- Nikos M.