drhagen drhagen - 11 days ago 5
Python Question

Recursive substitution in sympy

I have a sympy expression with multiple variables that need to be substituted out. The problem is that the some of the expressions to be substituted in also contain instances of variables that need to be substituted out.

from sympy import *
from sympy.abs import a,b, x,y

expr = a + b
replace = [[a, x+y], [b, 2*a]]

expr.subs(replace) # 2*a + x + y, I want 3*x + 3*y


If the replacement list is in the right order, it will apply each substitution sequentially, though in my real application I don't know what order would be appropriate:

expr.subs(reversed(replace)) # 3*x + 3*y


I can force the substitution by applying the substitution n times to either
expr
or
replace
, but that seems computationally wasteful:

result = expr
for _ in replace:
# Applying n times
result = result.subs(replace)


I was hoping for a
recursive
option to
subs
, but that doesn't seem to exist. Any better options?

Answer

If you do it in the correct order, the replacement will be performed iteratively (unless you use subs(replacement, simultaneous=True), which performs all the replacements at once).

Your problem then is ordering the replacements correctly. What you want is a topological sort of the replacements. Namely, each replacement is a node in a graph, and there is an edge from (old1, new1) to (old2, new2) if new1 contains old2 (i.e., it should be replaced first).

SymPy has an implementation of topological_sort in sympy.utilities.iterables. It takes a list of vertices and a list of edges (tuples of vertices). Say you have

replace = [(y, z + 1), (x, y + z), (z, a)]

We can create a list of edges with

from itertools import combinations
edges = [(i, j) for i, j in permutations(replace, 2) if i[1].has(j[0])]

Sorting this gives

>>> from sympy import default_sort_key, topological_sort
>>> topological_sort([replace, edges], default_sort_key)
[(x, y + z), (y, z + 1), (z, a)]

The third argument of topological_sort is a key used to break ties. Since SymPy objects don't have an implicit ordering defined on them (< and > raise TypeError in general), there is a sort key implementation called default_sort_key that provides a canonical and consistent (but arbitrary) sorting of SymPy objects.

In a situation like the one shown by 404 where there would be an infinite loop, topological_sort will alert you that there is a cycle

>>> replace = [(x, y+1), (y, x+1)]
>>> edges = [(i, j) for i, j in permutations(replace, 2) if i[1].has(j[0])]
>>> topological_sort([replace, edges], default_sort_key)
Traceback (most recent call last):
  File "<ipython-input-51-72f3bfcfd4ad>", line 1, in <module>
    topological_sort([replace, edges], default_sort_key)
  File "/Users/aaronmeurer/Documents/Python/sympy/sympy/sympy/utilities/iterables.py", line 882, in topological_sort
    raise ValueError("cycle detected")
ValueError: cycle detected

Honestly, this ought to just be implemented directly in subs via a keyword argument. See https://github.com/sympy/sympy/issues/6257.

Comments