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: 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]