4

次の状況を処理するには、統合アルゴリズムが必要です。

式ツリーの各ノードには、子のリスト (連想) またはセット (連想および可換) があります。特定のパターンに可能なすべての一致を取得したいと思います。

ここに例があります。+ が可換で * が可換でない行列を扱っていると仮定しましょう。

表現：A + B*C*D + E

または:Add(A, Mul(B, C, D), E)

パターン：X + Y*Z

2試合見た

X: A + E
Y: B
Z: C * D

X: A + E
Y: B * C
Z: D

質問: これを処理する標準アルゴリズムはありますか?

4

1 に答える 1

1

これを見て頭に浮かぶのは、交換可能な用語を一致させるためのパーティションとサブセットだけです。n 項を m > n 項に一致させる場合、m を n 部分、p に分割する必要があります。

次に、元のパターンに対してテストできる長さ p_i のサブセットが必要です。最も限定的な用語を見つけて、最初にその用語に一致させることは理にかなっているかもしれません。たとえば、mul が一致する場合、mul が存在するかどうかを確認できます...そうであれば、最初の問題は mul 部分と残りの 2 つの部分に分割されています。最も限定的な用語は、操作数が最も多い用語です。したがって、X + X*Y*Z + X*(Y+Z) の 2 つの mul 項は一致します。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]))]

マッピングを行う限り、2 進数で項目を選択できるようにします。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']}

クリス

于 2012-10-26T22:27:24.037 に答える