私はPythonで2つの文字列を持っています.
A m * B s / (A m + C m)
と
C m * B s / (C m + A m)
これらは両方とも順序なし集合 (A、C) と順序なし集合 (B) の同等の関数です。m と s は、同じユニット間で交換できるユニットを示しますが、別のユニットとは交換できません。
これまでのところ、A、B、および C の順列を実行し、eval と SymPy の == 演算子を使用してそれらをテストしています。これには複数の欠点があります。
この種の同等性をテストするPythonの方法はありますか? 任意の式で動作するはずです。
考えられるすべての順列を繰り返す代わりに、1つが存在すると想定して、それを構築しようとします。正しい方法で行われると、アルゴリズムの失敗は順列が存在しないことを意味すると私は信じています。
上記の式に適用されるアイデアの概要は次のとおりです。
させて：
str1 = "A m * B s / (A m + C m)"
str2 = "C m * B s / (C m + A m)"
式を同一にするセット（A、C）の順列を探しています。str2に最初に出現した順序に従って、AとCのラベルをX1とX2に変更します。
X1 = C
X2 = A
str2ではCがAの前に表示されるためです。次に、y[i]がstr1に最初に出現した順にi番目のシンボルAまたはCになるように配列Yを作成します。それで：
Y[1] = A
Y[2] = C
str1ではAがCの前に表示されるためです。
次に、AとCをX1とX2に置き換えて、str2からstr3を作成します。
str3 = "X1 m * B s / (X1 m + X2 m)"
そして、Y[i]の代わりにXiを使用し始めます。まず、X1はY [1]=Aになります。
str3_1 = "A m * Bs / (A m + X2 m)"
この段階で、str3_1とstr1を、Xiのいずれか（この場合はX2）の最初の出現まで比較します。これは、これら2つの文字列が等しいためです。
str3_1[:18] = "A m * B s / (A m + "
str1[:18] = "A m * B s / (A m + "
順列を作成するチャンスがあります。それらが等しくない場合は、適切な順列が存在しないことを証明し（順列は少なくともその置換を行う必要があるため）、非等価性を推測する可能性があります。しかし、それらは等しいので、次のステップに進み、Y [2]=Cの代わりにX2を使用します。
str3_2 = "A m * B s / (A m + C m)"
そして、これはstr1に等しいので、順列（A-> C、C-> A）があり、式の同等性を示しています。
これは、特定のケースに対するアルゴリズムのデモンストレーションにすぎませんが、一般化する必要があります。あなたがそれを得ることができる最低の順序が何であるかはわかりませんが、それはnよりも速いはずです！n個の変数ですべての順列を生成します。
単位の重要性を正しく理解していれば、順列によってどの変数を他の変数と交換できるかが制限されます。そのため、上記の式でAをCに置き換えることができます。これは、両方に「m」単位があるためですが、「s」単位を持つBには置き換えられないためです。これは次の方法で処理できます。
m単位を持たないすべてのシンボルを削除してstr1とstr2から式str1_mとstr2_mを作成し、str1_mとstr2_mに対して上記のアルゴリズムを実行します。構築が失敗した場合、順列は存在しません。構築が成功した場合は、その順列を保持し（m順列と呼びます）、s単位を持たないすべてのシンボルを削除してstr1とstr2からstr1_sとstr2_sを構築し、str1_sとstr2_sに対してアルゴリズムを再度実行します。建設が失敗した場合、それらは同等ではありません。それが成功した場合、最終的な順列はm-順列とs-順列の組み合わせになります（おそらくそれを構築する必要はありませんが、それが存在することを気にするだけです）。
これが私の以前の答えに基づいた単純化されたアプローチです。
2つの式が順列で同等である場合、一方を他方に運ぶ順列は、最初の文字列のi番目の記号（最初の出現のインデックス順に並べられた）を2番目の文字列のi番目の記号（ここでも最初の発生）。この原則を使用して、順列を作成し、それを最初の文字列に適用してから、2番目の文字列と等しいかどうかを確認できます。等しい場合は同等です。そうでない場合はそうではありません。
考えられる実装の1つは次のとおりです。
import re
# Unique-ify list, preserving order
def uniquify(l):
return reduce(lambda s, e: s + ([] if e in s else [e]), l, [])
# Replace all keys in replacements with corresponding values in str
def replace_all(str, replacements):
for old, new in replacements.iteritems():
str = str.replace(old, new)
return str
class Expression:
units = ["m", "s"]
def __init__(self, exp):
self.exp = exp
# Returns a list of symbols in the expression that are preceded
# by the given unit, ordered by first appearance. Assumes the
# symbol and unit are separated by a space. For example:
# Expression("A m * B s / (A m + C m)").symbols_for_unit("m")
# returns ['A', 'C']
def symbols_for_unit(self, unit):
sym_re = re.compile("(.) %s" % unit)
symbols = sym_re.findall(self.exp)
return uniquify(symbols)
# Returns a string with all symbols that have units other than
# unit "muted", that is replaced with the empty string. Example:
# Expression("A m * B s / (A m + C m)").mute_symbols_for_other_units("m")
# returns "A m * s / (A m + C m)"
def mute_symbols_for_other_units(self, unit):
other_units = "".join(set(self.units) - set(unit))
return re.sub("(.) ([%s])" % "".join(other_units), " \g<2>", self.exp)
# Returns a string with all symbols that have the given unit
# replaced with tokens of the form $0, $1, ..., by order of their
# first appearance in the string, and all other symbols muted.
# For example:
# Expression("A m * B s / (A m + C m)").canonical_form("m")
# returns "$0 m * s / ($0 m + $1 m)"
def canonical_form(self, unit):
symbols = self.symbols_for_unit(unit)
muted_self = self.mute_symbols_for_other_units(unit)
for i, sym in enumerate(symbols):
muted_self = muted_self.replace("%s %s" % (sym, unit), "$%s %s" % (i, unit))
return muted_self
# Define a permutation, represented as a dictionary, according to
# the following rule: replace $i with the ith distinct symbol
# occurring in the expression with the given unit. For example:
# Expression("C m * B s / (C m + A m)").permutation("m")
# returns {'$0':'C', '$1':'A'}
def permutation(self, unit):
enum = enumerate(self.symbols_for_unit(unit))
return dict(("$%s" % i, sym) for i, sym in enum)
# Return a string produced from the expression by first converting it
# into canonical form, and then performing the replacements defined
# by the given permutation. For example:
# Expression("A m * B s / (A m + C m)").permute("m", {"$0":"C", "$1":"A"})
# returns "C m * s / (C m + A m)"
def permute(self, unit, permutation):
new_exp = self.canonical_form(unit)
return replace_all(new_exp, permutation)
# Test for equality under permutation and muting of all other symbols
# than the unit provided.
def eq_under_permutation(self, unit, other_exp):
muted_self = self.mute_symbols_for_other_units(unit)
other_permuted_str = other_exp.permute(unit, self.permutation(unit))
return muted_self == other_permuted_str
# Test for equality under permutation. This is done for each of
# the possible units using eq_under_permutation
def __eq__(self, other):
return all([self.eq_under_permutation(unit, other) for unit in self.units])
e1 = Expression("A m * B s / (A m + C m)")
e2 = Expression("C m * B s / (C m + A m)")
e3 = Expression("A s * B s / (A m + C m)")
f1 = Expression("A s * (B s + D s) / (A m + C m)")
f2 = Expression("A s * (D s + B s) / (C m + A m)")
f3 = Expression("D s")
print "e1 == e2: ", e1 == e2 # True
print "e1 == e3: ", e1 == e3 # False
print "e2 == e3: ", e2 == e3 # False
print "f1 == f2: ", f1 == f2 # True
print "f1 == f3: ", f1 == f3 # False
ご指摘のとおり、これは数学的な同等性に関係なく、順列の下で文字列の同等性をチェックしますが、それは戦いの半分です。数式の標準形がある場合は、このアプローチを標準形の2つの式に使用できます。おそらく、sympyのSimplifyの1つでうまくいくかもしれません。
SymPy のsympify()関数に文字列を渡すと、シンボルが自動的に作成されます (すべてを定義する必要はありません)。
>>> from sympy import *
>>> x
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'x' is not defined
>>> sympify("x**2 + cos(x)")
x**2 + cos(x)
>>> sympify("diff(x**2 + cos(x), x)")
2*x - sin(x)