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

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

在实际应用中,链条更长,可能有数千种组合,并且应用数百种约束是相当计算密集的,因此我关注可伸缩性.

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

编辑: 也许这将澄清一点:在实际应用中,我正在从简单的基本块(如柱子,屋顶段,窗户等)组装建筑物的随机2D图片.约束限制了哪种块(及其旋转)可以组合在一起,因此得到的随机图像看起来很逼真,而不是随机混乱.

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

因为这些限制很难创造; 我希望可视化每个约束中所有块的组合看起来像什么,但只有通过所有约束的有效组合.因此我的问题.谢谢!

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)

哪个是发电机.

这里的重要区别是列表推导使用指定的标准和生成器创建列表,而仅提供生成器允许过滤器根据需要生成值.重要的机制是惰性评估,它实际上只归结为只评估表达式,因为它们的值变得必要.