Tools

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.

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]

Previous topic

Low-level multichoose

Next topic

Rankers

This Page