Проверка эквивалентности математических выражений в Python

Question

У меня есть две строки в Python,

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 ==. Это имеет несколько недостатков:

• для более сложных выражений мне нужно сгенерировать большое количество перестановок (в моем случае 8 вложенных в циклы)
• Мне нужно определить A, B, C как символы, что не является оптимальным, когда я не знаю, какие параметры у меня будут (поэтому я должен сгенерировать их все -> ужасно неэффективно и испортить мое пространство имен переменных)

Есть ли питонский способ проверки на такую ​​эквивалентность? Должно работать произвольное выражение.

Answer 1

Вместо того, чтобы перебирать все возможные перестановки, предположим, что он существует, и попытайтесь его построить. Я считаю, что если все сделано правильно, то сбой алгоритма будет означать отсутствие перестановки.

Вот схема идеи, примененной к вышеприведенным выражениям:

пусть:

str1 = "A m * B s / (A m + C m)"
str2 = "C m * B s / (C m + A m)"

Мы ищем перестановку множества (A, C), которая сделала бы выражения идентичными. Пометьте A и C как X1 и X2 в соответствии с порядком их первого появления в str2, поэтому:

X1 = C
X2 = A

потому что C появляется перед A в str2. Затем создайте массив Y так, чтобы y [i] был i-м символом A или C в порядке первого появления в str1. Итак:

Y[1] = A
Y[2] = C

Поскольку A появляется перед C в str1.

Теперь создайте str3 из str2, заменив A и C на X1 и X2:

str3 = "X1 m * B s / (X1 m + X2 m)"

А затем начните заменять X на Y [i]. Во-первых, X1 становится Y [1] = A:

str3_1 = "A m * Bs / (A m + X2 m)"

На этом этапе сравните str3_1 и str1 до первого вхождения любого из Си, в данном случае X2, так как эти две строки равны:

str3_1[:18] = "A m * B s / (A m + " 
str1[:18] = "A m * B s / (A m + "

У вас есть шанс построить перестановку. Если бы они были неравны, вы бы доказали, что подходящей перестановки не существует (потому что любая перестановка должна была бы произвести хотя бы эту замену) и могла бы вывести неэквивалентность. Но они равны, поэтому вы переходите к следующему шагу, заменяя X2 на Y [2] = C:

str3_2 = "A m * B s / (A m + C m)"

И это равно str1, так что у вас есть перестановка (A-> C, C-> A) и вы показали эквивалентность выражений.

Это всего лишь демонстрация алгоритма для конкретного случая, но его следует обобщить. Не уверен, какой самый низкий порядок вы могли бы получить его, но это должно быть быстрее, чем n! генерации всех перестановок по n переменным.

Если я правильно понимаю значение единиц, они ограничивают, какие переменные можно поменять местами с помощью перестановок. Таким образом, A может быть заменено на C в вышеприведенных выражениях, потому что оба имеют единицы 'm', но не те, которые имеют единицы 's' Вы можете справиться с этим следующим образом:

построить выражения str1_m и str2_m из str1 и str2, удалив все символы, не имеющие m единиц, а затем выполнить приведенный выше алгоритм для str1_m и str2_m. Если конструкция терпит неудачу, перестановка не существует. Если построение завершается успешно, сохраните эту перестановку (назовите ее m-перестановкой) и создайте str1_s и str2_s из str1 и str2, удалив все символы, которые не имеют s единиц, а затем снова выполните алгоритм для str1_s и str2_s. Если строительство терпит неудачу, они не эквивалентны. Если это удастся, окончательная перестановка будет представлять собой комбинацию m-перестановки и s-перестановки (хотя вам, вероятно, даже не нужно ее создавать, вас просто волнует, что она существует).

Answer 2

Вот упрощенный подход, основанный на моем предыдущем ответе.

Идея состоит в том, что если два выражения эквивалентны при перестановках, перестановка, переносящая одно в другое, должна отображать i-й символ в первой строке (упорядоченный по индексу первого появления) в i-й символ во второй строке(снова упорядочено по индексу первого появления).Этот принцип может быть использован для построения перестановки, применения ее к первой строке, а затем проверки на равенство со второй строкой - если они равны, они эквивалентны, в противном случае они не являются.

Вот одна из возможных реализаций:

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

Как вы указали, это проверяет эквивалентность строк при перестановках без учета математической эквивалентности, но это полдела.Если бы у вас была каноническая форма для математических выражений, вы могли бы использовать этот подход для двух выражений в канонической форме.Возможно, один из Simplify Симпи мог бы добиться цели.

Answer 3

Если вы передадите строку в функцию 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)

Answer 4

Я сделал это однажды, в одном симуляторе математических обзоров .. Ну, в моем случае я знал, какие переменные будут использоваться.

Итак, я проверил результат, поместив значения в переменные.

A = 10
B = 20
C = 30
m = Math.e
s = Math.pi

И так, решаем:

s1 = 'A m * B s / (A m + C m)'
s2 = 'C m * B s / (C m + A m)'

Если s1! = S2, доказано, что эквивалентности нет

С помощью этого метода невозможно сказать, что два выражения эквивалентны, Но вы можете сказать, что оба не эквивалентны

if s1 != s2:
   print "Not equivalent"
else:
   print "Try with another sample"

Хорошо .. Я надеюсь, что это поможет вам.

Answer 5

Это, как и все другие ответы на сегодняшний день, не является надежным решением проблемы, но вместо этого содержит более полезную информацию для нашего будущего дотошного друга, чтобы решить ее.

Я приведу сложный пример, используя формулу Эйлера https://en.wikipedia.org/wiki/Euler%27s_formula

Я уверен, что все остальные ответы о переполнении на сегодняшний день не получатся в моем примере.

Я показываю, что на моем примере все предложения на сайте sympy также терпят неудачу. (https://github.com/sympy/sympy/wiki/Faq)

#SOURCE FOR HELPERS:    https://github.com/sympy/sympy/wiki/Faq 
import sympy
import sympy.parsing.sympy_parser
ExampleExpressionString1 = 'exp( i*( (x0 - 1)*(x0 + 2) ) )'
ExampleExpressionSympy1 = sympy.parsing.sympy_parser.parse_expr(ExampleExpressionString1)

ExampleExpressionString2 = 'i*sin( (x0 - 1)*(x0 + 2) ) + cos( (x0 - 1)*(x0 + 2) )'
ExampleExpressionSympy2 = sympy.parsing.sympy_parser.parse_expr(ExampleExpressionString2)

print '(ExampleExpressionSympy1 == ExampleExpressionSympy2):'
print ' ', (ExampleExpressionSympy1 == ExampleExpressionSympy2)

print '(ExampleExpressionSympy1.simplify() == ExampleExpressionSympy2.simplify()):'
print ' ', (ExampleExpressionSympy1.simplify() == ExampleExpressionSympy2.simplify())

print '(ExampleExpressionSympy1.expand() == ExampleExpressionSympy2.expand()):'
print ' ', (ExampleExpressionSympy1.trigsimp() == ExampleExpressionSympy2.trigsimp())

print '(ExampleExpressionSympy1.trigsimp() == ExampleExpressionSympy2.trigsimp()):'
print ' ', (ExampleExpressionSympy1.trigsimp() == ExampleExpressionSympy2.trigsimp())

print '(ExampleExpressionSympy1.simplify().expand().trigsimp() == ExampleExpressionSympy2.simplify().expand().trigsimp()):'
print ' ', (ExampleExpressionSympy1.simplify().expand().trigsimp() == ExampleExpressionSympy2.simplify().expand().trigsimp())

БОЛЬШЕ ЗАМЕЧАНИЙ:

Я подозреваю, что эту проблему трудно решить в общем и целом. Чтобы правильно проверить математическую эквивалентность, вам нужно не только попробовать перестановки порядка, но и библиотеку математических эквивалентных преобразований и попробовать все эти перестановки.

Я, однако, считаю, что это может быть решаемой проблемой, потому что у Wolfram Alpha, похоже, есть раздел «альтернативное выражение», который, по-видимому, выполняет большую часть времени, предоставляя все перестановки для произвольных выражений, используя эти виды эквивалентностей.

В сумме:

Я предлагаю следующее с надеждой, что оно сломается:

import sympy
import sympy.parsing.sympy_parser
Expression.simplify().expand().trigsimp()