如何在字符串中找到多个 "holes" 的所有可能排列？

Question

我有以下初始字符串：

initial = "S + B + B"

和一个包含可能替换的字典：

replacements = { "S": ["0", "1"], "B": ["a", "b", "1"] }

并且我想编写一个函数 permute，在给定可接受的替换的情况下创建所有可能的排列：

def permute(initial, replacements):
    pass  # TODO

print(permute(initial, replacements))

应该输出以下内容：

["0 + a + a", "1 + a + a", "0 + a + b", ...]

一些注意事项：

如果在初始字符串中找到替换项，则保证它们具有键（例如，“S”在初始字符串中但不是替换字典中的键的情况将不会发生)
替换字典值可以是大于或等于 1 的任意长度（即非空）
我正在寻找与 Python 3 => 3.7 左右兼容的答案

我正在尝试编写它以在 program synthesis approach（增长步骤）中使用，但我很难将其翻译成 Python。非常感谢任何帮助！

Answer 1

您可以使用 itertools.product:

import itertools as it, re
initial = "S + B + B"
replacements = { "S": ["0", "1"], "B": ["a", "b", "1"] }
r = [re.sub('\w+', '{}', initial).format(*i) for i in it.product(*[replacements[i] for i in re.findall('\w+', initial)])]

输出：

['0 + a + a', '0 + a + b', '0 + a + 1', '0 + b + a', '0 + b + b', '0 + b + 1', '0 + 1 + a', '0 + 1 + b', '0 + 1 + 1', '1 + a + a', '1 + a + b', '1 + a + 1', '1 + b + a', '1 + b + b', '1 + b + 1', '1 + 1 + a', '1 + 1 + b', '1 + 1 + 1']

如何在字符串中找到多个 "holes" 的所有可能排列？

How do I find all possible permutations with multiple "holes" in a string?

python

permutation

python-3.x