Факторинг Полис в Симпи

Question

Я делаю очень простые вычисления вероятности получения подмножества X, Y, Z из набора AZ (с соответствующими вероятностями x, y, z).

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

Итак... имея это (очень простое выражение для вычисления вероятности получения подмножества X, Y, Z из множества AZ с соответствующими вероятностями x, y, z)

import sympy as sp

x, y, z = sp.symbols('x y z')

expression = (
    x * (1 - x) * y * (1 - x - y) * z +
    x * (1 - x) * z * (1 - x - z) * y +

    y * (1 - y) * x * (1 - y - x) * z +
    y * (1 - y) * z * (1 - y - z) * x +

    z * (1 - z) * y * (1 - z - y) * x +
    z * (1 - z) * x * (1 - z - x) * y
)

Я хочу получить что-то подобное

x * y * z * (6 * (1 - x - y - z) + (x + y) ** 2 + (y + z) ** 2 + (x + z) ** 2)

Поли, переписанный таким образом, чтобы иметь как можно меньше операций (+, -, *, **,...) насколько это возможно

---

Я старался factor(), collect(), simplify(), Но результат отличается от моих ожиданий. В основном я получаю

2*x*y*z*(x**2 + x*y + x*z - 3*x + y**2 + y*z - 3*y + z**2 - 3*z + 3)

Я знаю, что sympy может объединять полиномы в простые формы:

sp.factor(x**2 + 2*x*y + y**2)  # gives (x + y)**2

Но как заставить симпати сочетать многочлены из приведенных выше выражений?

---

Если это невыполнимая задача, может быть есть другие варианты?

Answer 1

Совокупность некоторых методов дает хороший ответ на этот раз. Было бы интересно посмотреть, работает ли эта стратегия чаще, чем не на уравнениях, которые вы генерируете, или, как видно из названия, на этот раз это просто удачный результат.

def iflfactor(eq):
    """Return the "I'm feeling lucky" factored form of eq."""
    e = Mul(*[horner(e) if e.is_Add else e for e in
        Mul.make_args(factor_terms(expand(eq)))])
    r, e = cse(e)
    s = [ri[0] for ri in r]
    e = Mul(*[collect(ei.expand(), s) if ei.is_Add else ei for ei in
        Mul.make_args(e[0])]).subs(r)
    return e

>>> iflfactor(eq)  # using your equation as eq
2*x*y*z*(x**2 + x*y + y**2 + (z - 3)*(x + y + z) + 3)
>>> _.count_ops()
15

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

>>> factor_terms(x/(z+z*y)+x/z)
x*(1 + 1/(y + 1))/z
>>> gcd_terms(x/(z+z*y)+x/z)
x*(y*z + 2*z)/(z*(y*z + z))

Для чего это стоит,

Крис

Answer 2

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

Однако в SymPy есть довольно много функций упрощения, которые вы можете попробовать. Тот, который вы не упомянули, который дает другой результат gcd_terms, который разлагает символический gcd ​​без выполнения расширений. Это дает

>>> gcd_terms(expression)
x*y*z*((-x + 1)*(-x - y + 1) + (-x + 1)*(-x - z + 1) + (-y + 1)*(-x - y + 1) + (-y + 1)*(-y - z + 1) + (-z + 1)*(-x - z + 1) + (-z + 1)*(-y - z + 1))

Еще одна полезная функция .count_ops, который считает количество операций в выражении. Например

>>> expression.count_ops()
47
>>> factor(expression).count_ops()
22
>>> e = x * y * z * (6 * (1 - x - y - z) + (x + y) ** 2 + (y + z) ** 2 + (x + z) ** 2)
>>> e.count_ops()
18

(Обратите внимание, что e.count_ops() не так, как вы рассчитывали, потому что SymPy автоматически распределяет 6*(1 - x - y - z) в 6 - 6*x - 6*y - 6*z).

Другие полезные функции:

• cse: Выполняет общее исключение подвыражения в выражении. Иногда вы можете упростить отдельные части, а затем собрать их вместе. Это также помогает в целом избежать дублирования вычислений.

• horner: Применяет схему Хорнера к полиному. Это минимизирует количество операций, если многочлен находится в одной переменной.

• factor_terms: Похожий на gcd_terms, Мне на самом деле не совсем понятно, в чем разница.

Обратите внимание, что по умолчанию simplify попробует несколько упрощений и вернет тот, который минимизирован count_ops,

Answer 3

У меня была аналогичная проблема, и я реализовал собственное решение, прежде чем наткнулся на это. Моя, похоже, работает намного лучше, сокращая количество операций. Однако у меня также есть набор коллекций в стиле грубой силы для всех комбинаций переменных. Таким образом, время выполнения растет сверхэкспоненциально по количеству переменных. OTOH, мне удалось запустить его на уравнениях с 7 переменными за небезосновательный (но далеко не в реальном времени) промежуток времени.

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

def collect_best(expr, measure=sympy.count_ops):
    # This method performs sympy.collect over all permutations of the free variables, and returns the best collection
    best = expr
    best_score = measure(expr)
    perms = itertools.permutations(expr.free_symbols)
    permlen = np.math.factorial(len(expr.free_symbols))
    print(permlen)
    for i, perm in enumerate(perms):
        if (permlen > 1000) and not (i%int(permlen/100)):
            print(i)
        collected = sympy.collect(expr, perm)
        if measure(collected) < best_score:
            best_score = measure(collected)
            best = collected
    return best

def product(args):
    arg = next(args)
    try:
        return arg*product(args)
    except:
        return arg

def rcollect_best(expr, measure=sympy.count_ops):
    # This method performs collect_best recursively on the collected terms
    best = collect_best(expr, measure)
    best_score = measure(best)
    if expr == best:
        return best
    if isinstance(best, sympy.Mul):
        return product(map(rcollect_best, best.args))
    if isinstance(best, sympy.Add):
        return sum(map(rcollect_best, best.args))

Чтобы проиллюстрировать производительность, в этой статье(платной, извините) есть 7 формул, которые представляют собой полиномы 5-й степени от 7 переменных с до 29 членов и 158 операций в развернутых формах. После применения обоихrcollect_best и @ smichr's iflfactor, количество операций в 7 формулах составляет:

[6, 15, 100, 68, 39, 13, 2]

а также

[32, 37, 113, 73, 40, 15, 2]

соответственно. iflfactor имеет на 433% операций больше, чем rcollect_bestпо одной из формул. Также количество операций в развернутых формулах:

[39, 49, 158, 136, 79, 27, 2]