Recursive substitution in sympy

Question

I have a simplex expression with several variables that need to be replaced. The problem is that some of the wildcard expressions also contain variable instances that need to be replaced.

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 correct order, it will apply each substitution sequentially, although in my real application I do not know which order will 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 this seems computationally wasteful:

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

I was hoping for a recursive subs option, but this does not seem to exist. Any better options?

Answer 1

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

Then your task organizes the replacements correctly. What you want is a topological view for substitutions. Namely, each replacement is a node in the 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 (vertex tuples). Let's say you

 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 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 to topological_sort is the key used to break ties. Since SymPy objects do not have implicit ordering on them ( < and > raise TypeError in general), there is an implementation of the sort key called default_sort_key , which provides canonical and sequential (but arbitrary) sorting of SymPy objects.

In a situation like the one shown in 404, where there will be an infinite loop, topological_sort warn you that there is a loop

 >>> 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 should just be implemented directly in subs using the keyword argument. See https://github.com/sympy/sympy/issues/6257 .

Answer 2

If there is a recursive option, it will presumably do the replacement until the expression stops changing. This is something you can do yourself; and I don’t think it’s wasteful, because sympy is also written in Python.

Here is a function that returns the result of the substitution along with its success indicator: whether the expression was reached in a stable form after substitutions. This will be false for substitution rules leading to an infinite loop, for example replace = [[x, y+1], [y, x+1]] .

 def recursive_sub(expr, replace): for _ in range(0, len(replace) + 1): new_expr = expr.subs(replace) if new_expr == expr: return new_expr, True else: expr = new_expr return new_expr, False 

Now res, _ = recursive_sub(expr, replace) returns 3*x + 3*y when used with your expr and replace .

Answer 3

I ran into the same problem and there is still no simple, general solution to this problem in SymPy.

Perhaps my quick and easy workaround will help:

Code prefix

 import sympy x, y = sympy.symbols("x, y") reps = [(y, x**2), (x, 2)] 

An example that shows that the order of the substitutions matters

Directly from the official SymPy documentation at http://docs.sympy.org/dev/modules/core.html#sympy.core.basic.Basic.subs

 >>> (x + y).subs(reps) 6 >>> (x + y).subs(reversed(reps)) x**2 + 2 

My workaround that works with any order of substitutions:

Just replace the variables more than once.

 >>> (x + y).subs(100 * reps) 6 >>> (x + y).subs(reversed(100 * reps)) 6 

Obviously, this only works for a fixed "depth of recursion", and I think that unnecessary calls (on top of those that actually change expression) can be very time consuming if you work with large expressions or a lot of permutations.