如何获得所有可能组合的数量？

Question

目标：我有一个字符串通常看起来像这样的“010”，我需要用所有可能的方式将零替换为 1 [ "010", "110", "111", "011"]
问题当我用 1 替换零时，我从左到右然后从右到左遍历字符串的字母。正如您在我所做的代码中看到的那样 number = number[::-1]。现在，这个方法实际上并没有涵盖所有的可能性。
我还需要从中间开始，或者可能使用 permutation method 但不确定如何在 python 中应用。
- 数学上有类似 factorial of the number of places/(2)!

A = '0111011110000'
B = '010101'
C = '10000010000001101'
my_list = [A,B,C]
for number in [A,B,C]:
    number = number[::-1]
    for i , n in enumerate(number):
        number = list(number)
        number[i] = '1'
        number = ''.join(number)
        if number not in my_list: my_list.append(number)


for number in [A,B,C]:
    for i , n in enumerate(number):
        number = list(number)
        number[i] = '1'
        number = ''.join(number)
        if number not in my_list: my_list.append(number)
print(len(my_list))
print(my_list)

Answer 1

嗯，您肯定会通过固定索引组合的传统实现得到其他答案，但由于我们只处理“0”和“1”，您可以使用下一个 hack：

source = "010100100001100011"
pattern = source.replace("0", "{}")
count = source.count("0")
combinations = [pattern.format(*f"{i:0{count}b}") for i in range(1 << count)]

基本上，我们计算源中零的数量，然后在范围内迭代，其中 limit 是具有此设置位数量的数字，并将二进制形式的每个数字解压缩为一个模式。

如果我们也为二进制转换预定义模式应该会稍微快一些:

source = "010100100001100011"
pattern = source.replace("0", "{}")
count = source.count("0")
fmt = f"{{:0{count}b}}"
result = [pattern.format(*fmt.format(i)) for i in range(1 << count)]

Upd. 不清楚您是需要生成所有可能的组合还是只获取数字，所以最初我提供了生成它们的代码，但是如果您仔细查看我的方法我使用 1 << count 获取所有可能组合的数量，其中 count 是源字符串中 '0' 个字符的数量。所以如果你只需要数字，代码是下一个：

source = "010100100001100011"
number_of_combinations = 1 << source.count("0")

或者，您也可以使用 2 ** source.count("0")，但通常功率比二进制移位慢得多，所以我建议使用我最初建议的选项。

Answer 2

您可以使用分离出零，然后使用 itertools.product -

from itertools import product
x = '0011'
perm_elements = [('0', '1') if digit == '0' else ('1', ) for digit in x]
print([''.join(x) for x in product(*perm_elements)])
['0011', '0111', '1011', '1111']

如果您只需要此类组合的数量，而不是列表本身 - 那应该只是 2 ** x.count('0')

Answer 3

根据你的objective你可以这样做以获得预期的结果。

A = '0111011110000'
B = '010'
C = '10000010000001101'
my_list = [A, B, C]
new_list = []
        
for key, number in enumerate(my_list):
    for key_item, num in enumerate(number):
        item_list = [i for i in number]
        item_list[key_item] = "1"
        new_list.append(''.join(item_list))
print(len(new_list))
print(new_list)

Answer 4

对于字符串中每个包含零的位置，您可以将其替换为 1，也可以不替换。这创建了组合。因此，您可以根据先前的替换结果，通过将每个“0”位置的替换添加为“1”，逐步构建结果字符串列表：

def zeroTo1(S):
    result = [S]                 # start with no replacement
    for i,b in enumerate(S):
        if b != '0': continue                         # only for '0' positions
        result += [r[:i]+'1'+r[i+1:] for r in result] # add replacements
    return result

print(zeroTo1('010'))
['010', '110', '011', '111']

如果允许您使用库，可以使用 itertools 的乘积函数直接为您组合零替换：

from itertools import product
def zeroTo1(S):
    return [*map("".join,product(*("01"[int(b):] for b in S)))]

通过将字符串连接函数映射到其输出，乘积函数生成的 1 和 0 的元组被组装成单独的字符串。

Answer 5

我们也可以对这个问题使用递归解决方案，我们遍历字符串，如果看到“0”，则将其更改为“1”，然后在这个新字符串上开始另一个分支：

s = "010100100001100011"

def perm(s, i=0, result=[]):
    if i < len(s):
        if s[i] == "0":
            t = s[:i]+"1"+s[i+1:]
            result.append(t)
            perm(t, i+1, result)
        perm(s, i+1, result)

res = [s]
perm(s, 0, res)
print(res)

如何获得所有可能组合的数量？

How to get a the number of all possible combinations?

python

math

probability