7

我正在做一个非常简单的概率计算，从 AZ 集合中获取 X、Y、Z 的子集（具有相应的概率 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

但是如何使 sympy 从上面的表达式中组合多项式呢？

如果这是 sympy 中不可能完成的任务，是否还有其他选择？

4

3 回答 3

7

这次将一些方法放在一起恰好给出了一个很好的答案。看看这个策略是否经常在你生成的方程上起作用，或者顾名思义，这一次这只是一个幸运的结果，将会很有趣。

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 会更加努力地提取常用术语，同时保留表达式的原始结构，就像您手动操作一样（即在 Adds 中寻找可以提取的常用术语） .

>>> 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))

物有所值，

克里斯

于 2013-03-04T02:54:22.830 回答
3

据我所知，没有任何功能可以做到这一点。我相信这实际上是一个非常困难的问题。有关它的一些讨论，请参阅减少对简单表达式的操作数。

但是，您可以尝试 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)to 6 - 6*x - 6*y - 6*z）。

其他有用的功能：

  • cse：对表达式执行公共子表达式消除。有时您可以简化各个部分，然后将它们重新组合在一起。这通常也有助于避免重复计算。

  • horner：将霍纳方案应用于多项式。如果多项式在一个变量中，这将最小化操作次数。

  • factor_terms: 类似gcd_terms。我实际上并不完全清楚有什么区别。

请注意，默认情况下，simplify将尝试几种简化，并返回被 最小化的那个count_ops。

于 2013-03-03T22:25:39.743 回答
1

我遇到了类似的问题，并最终在我偶然发现这个问题之前实施了我自己的解决方案。我的似乎在减少操作次数方面做得更好。但是，我的也对所有变量组合进行了蛮力风格的集合。因此，它的运行时间在变量数量上呈超指数增长。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 个公式，它们是 7 个变量的 5 次多项式，具有多达 29 个项和 158 个扩展形式的运算。在同时应用rcollect_best和 @smichr'siflfactor后，7 个公式中的运算次数为：

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

和

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

分别。 iflfactor比rcollect_best公式之一多 433% 的操作。此外，扩展公式中的操作数为：

[39, 49, 158, 136, 79, 27, 2]
于 2019-09-06T20:36:41.063 回答