Transitive ideal closure tool

sage.combinat.tools.transitive_ideal(f, x)

Return a list of all elements reachable from $x$ in the abstract reduction system whose reduction relation is given by the function $f$.

In more elementary terms:

If $S$ is a set, and $f$ is a function sending every element of $S$ to a list of elements of $S$, then we can define a digraph on the vertex set $S$ by drawing an edge from $s$ to $t$ for every $s\in S$ and every $t\in f(s)$.

If $x\in S$, then an element $y\in S$ is said to be reachable from $x$ if there is a path $x\to y$ in this graph.

Given $f$ and $x$, this method computes the list of all elements of $S$ reachable from $x$.

Note that if there are infinitely many such elements, then this method will never halt.

For more powerful versions, see sage.combinat.backtrack

EXAMPLES:

Sage

sage: f = lambda x: [x-1] if x > 0 else []
sage: sage.combinat.tools.transitive_ideal(f, 10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

>>> from sage.all import *
>>> f = lambda x: [x-Integer(1)] if x > Integer(0) else []
>>> sage.combinat.tools.transitive_ideal(f, Integer(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]