在 Sympy 中部分分解表达式 [英] Partially factoring an expression in Sympy

问题描述

假设我有一个 .我知道我可以像这样简化表达式: .但是，sympy.simplify 和 sympy.factor 都返回原始表达式.

Suppose I have an expression of the form . I know that I can simplify the expression like so: . However, sympy.simplify and sympy.factor both return the original expression.

为了解决这个问题，我一直在低级别对表达式进行操作:

To work around this, I've been operating on the expression at a low level:

factor_map = defaultdict(set)
additive_terms = expr.as_coeff_add()[-1]
for term1, term2 in combinations(additive_terms, 2):
    common_terms = (
        set(term1.as_coeff_mul()[-1])
        & set(term2.as_coeff_mul()[-1])
    )
    if common_terms:
        common_factor = sympy.Mul(*common_terms)
        factor_map[common_factor] |= {term1, term2}

factor_map 现在看起来像这样:

{
    a: {a⋅x, -a⋅y}, 
    b: {b⋅x, -b⋅y}, 
    c: {-c⋅x, c⋅y}, 
    x: {a⋅x, b⋅x, -c⋅x}, 
    y: {-a⋅y, -b⋅y, c⋅y}
}

我按照词条所代表的操作次数对其进行排序:

I sort it by the number of operations represented by the terms:

factor_list = sorted(
    factor_map.items(),
    key = lambda i: (i[0].count_ops() + 1) * len(i[1])
)[::-1]

然后我只是重建表达式:

I then just rebuild the expression:

used = set()
new_expr = 0
for item in factor_list:
    factor = item[0]
    appearances = item[-1]
    terms = 0
    for instance in appearances:
        if instance not in used:
            terms += instance.as_coefficient(factor)
            used.add(instance)
    new_expr += factor * terms
for term in set(additive_terms) - used:
    new_expr += term

这给出了 new_expr = d + x*(a + b - c) + y*(-a - b + c).不是很好，但更好.

This gives new_expr = d + x*(a + b - c) + y*(-a - b + c). Not great, but better.

我还可以通过将加性项的每个组合彼此相除，检查结果是否为数字，并使用该信息进一步将输出减少到 new_expr = d + (x - y) 来改进这一点*(a + b - c).

I can also improve on this by dividing each combination of additive terms by each other, checking if the result is a number, and using that information to further reduce the output to new_expr = d + (x - y)*(a + b - c).

我还尝试将 sympy.factor 应用于所有可能的附加项组合，但显然对于任何相当大的表达式来说，这很快就会爆炸.

I've also tried to apply sympy.factor to every possible combination of additive terms, but obviously that blows up very quickly for any reasonably big expression.

这是一个在附加项集的所有分区上使用 sympy.factor 的实现(从 这个答案):

Here's an implementation that uses sympy.factor on all partitions of the set of additive terms (partitions function borrowed from this answer):

def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller


def partial_factor(expr):
    args = list(expr.as_coeff_add()[-1])
    # Groupings is just a cache to avoid duplicating factor operations
    groupings = {}

    unique = set()

    for p in partition(args):
        new_expr = 0
        for group in p:
            add_group = sympy.Add(*group)
            new_expr += groupings.setdefault(add_group, sympy.factor(add_group))
        unique.add(new_expr)
    return sorted(unique, key=sympy.count_ops)[0]

对于像 a*x + b*y + c*z + d + e*x + f*y + h*z 这样的表达式，在我的电脑上运行需要 7.8 秒，而另一种方法需要 378 微秒并给出相同的结果.似乎应该有一种方法比第一种方法更严格，而不需要花费 20,000 倍的时间来解决它.

For an expression like a*x + b*y + c*z + d + e*x + f*y + h*z, it takes 7.8 seconds to run on my computer, whereas the other method takes 378 microseconds and gives the same result. Seems like there should be a way to be more rigorous than the first method without taking 20,000 times longer to solve it.

我觉得得到我想要的东西不应该这么难.有没有更简单的方法来做到这一点?

I feel like it shouldn't be this hard to get what I want. Is there an easier way to do this?

推荐答案

这个类似的问题 有一个涉及 func 参数到 collect() 的答案.它似乎也适用于这种特殊情况，尽管您必须明确提及 d:

This similar question has an answer involving the func parameter to collect(). It seems to work in this particular case as well, although you have to explicitly mention d:

from sympy import *
a, b, c, d, x, y = symbols('a, b, c, d, x, y')
expr = a * x + b * x - c * x - a * y - b * y + c * y + d
collect(expr, d, func=factor)
=> d + (x - y)*(a + b - c)

这在这种特定情况下有帮助，但不存在更通用和自动的解决方案.

This helps in this specific case, however a more general and automatic solution does not exist.

此外，除了现有的参数之外，我在任何地方都找不到此 func 参数的任何文档.

Also I could not find any documentation for this func parameter anywhere, other than it existing.

Github issue 跟踪这个问题

这篇关于在 Sympy 中部分分解表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！