在Python中测试数学表达式的等效性
||
我在Python中有两个字符串，
A m * B s / (A m + C m)
C m * B s / (C m + A m)
没有找到相关结果
已邀请:
5 个回复
森含械
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豆兢
我们正在寻找可以使表达式相同的集合（A，C）的置换。根据它们在str2中首次出现的顺序将A和C重新标记为X1和X2，因此：因为在str2中C出现在A之前。接下来，创建数组Y，以使y [i]按照在str1中首次出现的顺序是第i个符号A或C。所以：因为在str1中A出现在C之前。 现在通过用X1和X2替换A和C从str2构造str3：然后开始用Xi代替Y [i]。首先，X1变为Y [1] = A：在此阶段，将str3_1和str1比较到任何Xi的第一个匹配项（在本例中为X2），因为这两个字符串相等：您有机会构建排列。如果它们不相等，那么您将证明不存在适当的排列（因为任何排列都必须至少进行该替换），并且可以推论不等式。但是它们是相等的，因此您继续下一步，将X2替换为Y [2] = C：这等于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排列的组合（尽管您可能甚至不需要构造它，只要关心它的存在即可）。稳赣苍卯改
函数，它将自动为您创建符号（无需全部定义它们）。拭十年
因此，我们解决了：如果s1！= s2，则证明不存在等价关系 用这种方法不可能说两个表达式是相等的， 但您可以说两者都不相等好吧..我希望这可以对您有所帮助。倪蕊悲潍
更多说明： 我怀疑这是一个普遍且可靠地解决的难题。为了正确地检查数学等价关系，您不仅必须尝试排序，而且还必须拥有一个数学等价变换库，并且还必须尝试所有这些变换。 但是，我确实相信这可能是一个可解决的问题，因为Wolfram Alpha似乎具有“替代表达式”部分，这似乎可以解决大多数情况下使用此类等效项在任意表达式上提供所有排列的问题。 总结： 我建议以下内容，并期望它会破裂：