Factorización parcial de una expresión en Sympy

Supongamos que tengo una expresión de la forma Primera forma . Sé que puedo simplificar la expresión así: Segunda forma . Sin embargo, sympy.simplify y sympy.factor devuelven la expresión original.

Para solucionar esto, he estado operando en la expresión en un nivel bajo:

 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 ahora se ve así:

 { 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} } 

Lo ordeno por el número de operaciones representadas por los términos:

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

Entonces simplemente reconstruyo la expresión:

 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 

Esto le da a new_expr = d + x*(a + b - c) + y*(-a - b + c) . No es genial, pero mejor.

También puedo mejorar esto al dividir cada combinación de términos aditivos entre sí, verificando si el resultado es un número y usar esa información para reducir aún más la salida a new_expr = d + (x - y)*(a + b - c) .

También he intentado aplicar sympy.factor a todas las combinaciones posibles de términos aditivos, pero obviamente eso explota muy rápidamente para cualquier expresión razonablemente grande.


Edición: Aquí hay una implementación que usa sympy.factor en todas las particiones del conjunto de términos aditivos (función de particiones tomada de esta respuesta ):

 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] 

Para una expresión como a*x + b*y + c*z + d + e*x + f*y + h*z , se tarda 7.8 segundos en ejecutarse en mi computadora, mientras que el otro método toma 378 microsegundos y da la mismo resultado Parece que debería haber una manera de ser más riguroso que el primer método sin demorarse 20,000 veces más en resolverlo.


Siento que no debería ser tan difícil conseguir lo que quiero. ¿Hay alguna forma más fácil de hacer esto?

Es difícil sugerir una estrategia de “factorización parcial” que funcione la mayor parte del tiempo. Aquí hay una cosa para probar, diseñada con su ejemplo en mente (un polinomio de varias variables).

Dada una expresión: Intenta factorizarlo. Si no tiene éxito, mire el coeficiente de cada símbolo que contiene; El método Expr.coeff(Symbol) hace eso. El símbolo con el coeficiente más pequeño (medido por el número de símbolos contenidos) se considera un obstáculo para la factorización y se elimina de la expresión. Repetir.

Esta lógica se codifica a continuación, y el partial_factor(a*x + b*x - c*x - a*y - b*y + c*y + d) devuelve d + (x - y)*(a + b - c) .

 def partial_factor(expr): to_factor = expr non_factorable = 0 while to_factor != 0: if factor(to_factor) != to_factor: return factor(to_factor) + non_factorable coeffs = {v: to_factor.coeff(v) for v in to_factor.free_symbols} min_size = min([len(coeffs[v].free_symbols) for v in coeffs]) for v in coeffs: if len(coeffs[v].free_symbols) == min_size: non_factorable += v*coeffs[v] to_factor -= v*coeffs[v] break return expr