Transitive ideal closure tool

sage.combinat.tools.transitive_ideal(f, x)[source]

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]

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