StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is a simplified approach based on my previous answer. </p> <p>The idea is that if two expressions are equivalent under permutations, the permutation carrying one to the other must map the ith symbol in the first string (ordered by index of first occurrence) to the ith symbol in the second string (again ordered by index of first occurrence). This principle can be used to construct a permutation, apply it to the first string and then check for equality with the second string - if they are equal they are equivalent, otherwise they are not.</p> <p>Here is one possible implementation:</p> <pre><code>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 </code></pre> <p>As you pointed out, this checks for string equivalence under permutations without any regard to mathematical equivalence, but it is half the battle. If you had a canonical form for mathematical expressions, you could use this approach on two expressions in canonical form. Perhaps one of sympy's <a href="http://docs.sympy.org/dev/modules/simplify.html" rel="nofollow">Simplify</a> could do the trick. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload