python - 快速生成带约束的组合的方法？

Question

我有一个生成器函数，可以创建列表的笛卡尔积。真正的应用程序使用更复杂的对象，但它们可以用字符串表示:

import itertools

s1 = ['a', 'b']
s2 = ['c', 'd', 'e', 'f']
s3 = ['c', 'd', 'e', 'f']
s4 = ['g']

p = itertools.product(*[s1,s2,s3,s4])
names = [''.join(s) for s in p]

在这个例子中，结果是 32 个字符的组合:

names
['accg', 'acdg', 'aceg', 'acfg', 'adcg', 'addg', 'adeg', 'adfg', 'aecg',
 'aedg', 'aeeg', 'aefg', 'afcg', 'afdg', 'afeg', 'affg', 'bccg', 'bcdg',
 'bceg', 'bcfg', 'bdcg', 'bddg', 'bdeg', 'bdfg', 'becg', 'bedg', 'beeg',
 'befg', 'bfcg', 'bfdg', 'bfeg', 'bffg']

现在，假设我有一些限制，某些字符组合是非法的。例如，假设只允许包含正则表达式 '[ab].c' 的字符串。 ('a' 或 'b' 后跟任何字母后跟 'c')

应用这些约束后，我们只剩下 8 个字符串的缩减集:

import re
r = re.compile('[ab].c')
filter(r.match, names)
['accg', 'adcg', 'aecg', 'afcg', 'bccg', 'bdcg', 'becg', 'bfcg']

在实际应用中，链更长，可能有数千种组合，并且应用数百种约束在计算上相当密集，因此我担心可伸缩性。

现在我正在检查每一个组合并检查其有效性。是否存在可以加速此过程的算法/数据结构？

编辑:也许这会澄清一点:在实际应用中，我从简单的基本 block (如柱子、屋顶部分、 window 等)组装随机的 2D 建筑物图片。这些约束限制了可以将哪种 block (及其旋转)组合在一起，因此生成的随机图像看起来很逼真，而不是随机困惑。

给定的约束可以包含多种模式组合。但是在所有这些组合中，许多组合是无效的，因为不同的约束会禁止其中的某些部分。所以在我的示例中，一个约束将包含上述字符的完整笛卡尔积。第二个约束是'[ab].c'；第二个约束减少了我需要考虑的第一个约束的有效组合数量。

因为这些约束很难创建；我希望可视化每个约束中 block 的所有组合是什么样的，但只有通过所有约束的有效组合。因此我的问题。谢谢!

Answer 1

尝试只提供直接生成名称的迭代器来过滤，如下所示:

import itertools
import re

s1 = ['a', 'b']
s2 = ['c', 'd', 'e', 'f']
s3 = ['c', 'd', 'e', 'f']
s4 = ['g']

p = itertools.product(*[s1,s2,s3,s4])
r = re.compile('[ab].c')
l = filter(r.search, (''.join(s) for s in p))
print(list(l))

那样的话，它不应该在内存中组装完整的组合集，它只会保留符合条件的组合。可能还有另一种方法。

编辑:

与原始版本的主要区别之一是:

[''.join(s) for s in p]

这是一个列表理解，我们使用:

(''.join(s) for s in p)

这是一个发电机。

这里的重要区别在于，列表理解使用指定的条件和生成器创建列表，而仅提供生成器允许过滤器根据需要生成值。重要的机制是lazy evaluation ，这实际上归结为仅在表达式的值变得必要时才对其求值。