drhagen - 1 year ago 97
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?

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download