我需要一个统一算法来处理以下情况。
我的表达式树中的每个节点都有一个列表(关联的)或一组(关联的和可交换的)子节点。我想获得特定模式的所有可能匹配项。
这是一个例子。让我们假设我们正在处理矩阵，因此 + 是可交换的，而 * 是非可交换的
表达式:A + B*C*D + E
或者:Add(A, Mul(B, C, D), E)
模式:X + Y*Z
我看到两场比赛
X: A + E
Y: B
Z: C * D
X: A + E
Y: B * C
Z: D
问题:是否有任何标准算法可以处理这个问题？
最佳答案
当我看到这是用于匹配可交换项的分区和子集时，我想到的所有内容。如果要将 n 个术语与 m > n 个术语匹配，则必须将 m 划分为 n 个部分，即 p。
然后你想要长度 p_i 的子集，然后可以针对你的原始模式进行测试。找到最严格的术语并首先匹配该术语可能是有意义的。例如，如果 mul 要匹配，您可以查看是否有 muls 存在……如果是，那么您的初始问题已分为两部分:mul 部分和其余部分。最严格的术语是操作次数最多的术语。所以 X + X*Y*Z + X*(Y+Z) 这两个多项式并列；平局可能会被打破，以支持更复杂的 Add。所以也许 op_count 和操作类型的数量可能是复杂性度量。
在 SymPy 中:
>>> pat = X + X*Y*Z + X*(Y+Z)
>>> [(p.count_ops(), p.count_ops(visual=True).free_symbols) for p in Add.make_args(pat)]
[(0, set([])), (2, set([MUL])), (2, set([ADD, MUL]))]
至于制定映射，让二进制数字为您选择项目可以工作。再次在 SymPy 中使用
from sympy.utilities.iterables import reshape, runs, permutations 生效:>>> N=list('ABC')
>>> M=list('abcde')
>>> n=[1]*len(N)
>>> m=[1]*len(M)
>>> n.extend([0]*(len(m) - len(n)))
>>> grouper = lambda x, xx: x==xx==0 or x==0 and xx==1
>>> demo = [1, 0, 0, 1, 1]
>>> runs(demo, grouper)
[[1, 0, 0], [1], [1]]
>>> nn=n[1:] # the first one will stay put; shuffle the rest
>>> for p in permutations(nn):
... P = [1]+list(p)
... shape = [[len(r)] for r in runs(P, grouper)]
... print dict(zip(N, reshape(M, shape)[0]))
{'A': ['a'], 'C': ['c', 'd', 'e'], 'B': ['b']}
{'A': ['a'], 'C': ['c', 'd', 'e'], 'B': ['b']}
{'A': ['a'], 'C': ['d', 'e'], 'B': ['b', 'c']}
{'A': ['a'], 'C': ['e'], 'B': ['b', 'c', 'd']}
{'A': ['a'], 'C': ['d', 'e'], 'B': ['b', 'c']}
{'A': ['a'], 'C': ['e'], 'B': ['b', 'c', 'd']}
{'A': ['a'], 'C': ['c', 'd', 'e'], 'B': ['b']}
{'A': ['a'], 'C': ['c', 'd', 'e'], 'B': ['b']}
{'A': ['a'], 'C': ['d', 'e'], 'B': ['b', 'c']}
{'A': ['a'], 'C': ['e'], 'B': ['b', 'c', 'd']}
{'A': ['a'], 'C': ['d', 'e'], 'B': ['b', 'c']}
{'A': ['a'], 'C': ['e'], 'B': ['b', 'c', 'd']}
{'A': ['a', 'b'], 'C': ['d', 'e'], 'B': ['c']}
{'A': ['a', 'b'], 'C': ['e'], 'B': ['c', 'd']}
{'A': ['a', 'b'], 'C': ['d', 'e'], 'B': ['c']}
{'A': ['a', 'b'], 'C': ['e'], 'B': ['c', 'd']}
{'A': ['a', 'b', 'c'], 'C': ['e'], 'B': ['d']}
{'A': ['a', 'b', 'c'], 'C': ['e'], 'B': ['d']}
{'A': ['a', 'b'], 'C': ['d', 'e'], 'B': ['c']}
{'A': ['a', 'b'], 'C': ['e'], 'B': ['c', 'd']}
{'A': ['a', 'b'], 'C': ['d', 'e'], 'B': ['c']}
{'A': ['a', 'b'], 'C': ['e'], 'B': ['c', 'd']}
{'A': ['a', 'b', 'c'], 'C': ['e'], 'B': ['d']}
{'A': ['a', 'b', 'c'], 'C': ['e'], 'B': ['d']}
克里斯
关于programming-languages - 基于列表的树的统一算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13092092/