Recursively Enumerated Sets

A set \(S\) is called recursively enumerable if there is an algorithm that enumerates the members of \(S\). We consider here the recursively enumerated sets that are described by some seeds and a successor function successors. The successor function may have some structure (symmetric, graded, forest) or not. The elements of a set having a symmetric, graded or forest structure can be enumerated uniquely without keeping all of them in memory. Many kinds of iterators are provided in this module: depth first search, breadth first search and elements of given depth.

See Wikipedia article Recursively_enumerable_set.

See the documentation of RecursivelyEnumeratedSet() below for the description of the inputs.

AUTHORS:

  • Sébastien Labbé, April 2014, at Sage Days 57, Cernay-la-ville

EXAMPLES:

No hypothesis on the structure

What we mean by “no hypothesis” is that the set is not known to be a forest, symmetric, or graded. However, it may have other structure, such as not containing an oriented cycle, that does not help with the enumeration.

In this example, the seed is 0 and the successor function is either +2 or +3. This is the set of nonnegative linear combinations of 2 and 3:

sage: succ = lambda a:[a+2,a+3]
sage: C = RecursivelyEnumeratedSet([0], succ)
sage: C
A recursively enumerated set (breadth first search)

>>> from sage.all import *
>>> succ = lambda a:[a+Integer(2),a+Integer(3)]
>>> C = RecursivelyEnumeratedSet([Integer(0)], succ)
>>> C
A recursively enumerated set (breadth first search)

Breadth first search:

sage: it = C.breadth_first_search_iterator()
sage: [next(it) for _ in range(10)]
[0, 2, 3, 4, 5, 6, 7, 8, 9, 10]

>>> from sage.all import *
>>> it = C.breadth_first_search_iterator()
>>> [next(it) for _ in range(Integer(10))]
[0, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Depth first search:

sage: it = C.depth_first_search_iterator()
sage: [next(it) for _ in range(10)]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]

>>> from sage.all import *
>>> it = C.depth_first_search_iterator()
>>> [next(it) for _ in range(Integer(10))]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]

Symmetric structure

The origin (0, 0) as seed and the upper, lower, left and right lattice point as successor function. This function is symmetric since \(p\) is a successor of \(q\) if and only if \(q\) is a successor or \(p\):

sage: succ = lambda a: [(a[0]-1,a[1]), (a[0],a[1]-1), (a[0]+1,a[1]), (a[0],a[1]+1)]
sage: seeds = [(0,0)]
sage: C = RecursivelyEnumeratedSet(seeds, succ, structure='symmetric', enumeration='depth')
sage: C
A recursively enumerated set with a symmetric structure (depth first search)

>>> from sage.all import *
>>> succ = lambda a: [(a[Integer(0)]-Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]-Integer(1)), (a[Integer(0)]+Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]+Integer(1))]
>>> seeds = [(Integer(0),Integer(0))]
>>> C = RecursivelyEnumeratedSet(seeds, succ, structure='symmetric', enumeration='depth')
>>> C
A recursively enumerated set with a symmetric structure (depth first search)

In this case, depth first search is the default enumeration for iteration:

sage: it_depth = iter(C)
sage: [next(it_depth) for _ in range(10)]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9)]

>>> from sage.all import *
>>> it_depth = iter(C)
>>> [next(it_depth) for _ in range(Integer(10))]
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9)]

Breadth first search:

sage: it_breadth = C.breadth_first_search_iterator()
sage: [next(it_breadth) for _ in range(13)]
[(0, 0),
 (-1, 0), (0, -1), (1, 0), (0, 1),
 (-2, 0), (-1, -1), (-1, 1), (0, -2), (1, -1), (2, 0), (1, 1), (0, 2)]

>>> from sage.all import *
>>> it_breadth = C.breadth_first_search_iterator()
>>> [next(it_breadth) for _ in range(Integer(13))]
[(0, 0),
 (-1, 0), (0, -1), (1, 0), (0, 1),
 (-2, 0), (-1, -1), (-1, 1), (0, -2), (1, -1), (2, 0), (1, 1), (0, 2)]

Levels (elements of given depth):

sage: sorted(C.graded_component(0))
[(0, 0)]
sage: sorted(C.graded_component(1))
[(-1, 0), (0, -1), (0, 1), (1, 0)]
sage: sorted(C.graded_component(2))
[(-2, 0), (-1, -1), (-1, 1), (0, -2), (0, 2), (1, -1), (1, 1), (2, 0)]

>>> from sage.all import *
>>> sorted(C.graded_component(Integer(0)))
[(0, 0)]
>>> sorted(C.graded_component(Integer(1)))
[(-1, 0), (0, -1), (0, 1), (1, 0)]
>>> sorted(C.graded_component(Integer(2)))
[(-2, 0), (-1, -1), (-1, 1), (0, -2), (0, 2), (1, -1), (1, 1), (2, 0)]

Graded structure

Identity permutation as seed and permutohedron_succ as successor function:

sage: succ = attrcall("permutohedron_succ")
sage: seed = [Permutation([1..5])]
sage: R = RecursivelyEnumeratedSet(seed, succ, structure='graded')
sage: R
A recursively enumerated set with a graded structure (breadth first search)

>>> from sage.all import *
>>> succ = attrcall("permutohedron_succ")
>>> seed = [Permutation((ellipsis_range(Integer(1),Ellipsis,Integer(5))))]
>>> R = RecursivelyEnumeratedSet(seed, succ, structure='graded')
>>> R
A recursively enumerated set with a graded structure (breadth first search)

Depth first search iterator:

sage: it_depth = R.depth_first_search_iterator()
sage: [next(it_depth) for _ in range(5)]
[[1, 2, 3, 4, 5],
 [1, 2, 3, 5, 4],
 [1, 2, 5, 3, 4],
 [1, 2, 5, 4, 3],
 [1, 5, 2, 4, 3]]

>>> from sage.all import *
>>> it_depth = R.depth_first_search_iterator()
>>> [next(it_depth) for _ in range(Integer(5))]
[[1, 2, 3, 4, 5],
 [1, 2, 3, 5, 4],
 [1, 2, 5, 3, 4],
 [1, 2, 5, 4, 3],
 [1, 5, 2, 4, 3]]

Breadth first search iterator:

sage: it_breadth = R.breadth_first_search_iterator()
sage: [next(it_breadth) for _ in range(5)]
[[1, 2, 3, 4, 5],
 [2, 1, 3, 4, 5],
 [1, 3, 2, 4, 5],
 [1, 2, 4, 3, 5],
 [1, 2, 3, 5, 4]]

>>> from sage.all import *
>>> it_breadth = R.breadth_first_search_iterator()
>>> [next(it_breadth) for _ in range(Integer(5))]
[[1, 2, 3, 4, 5],
 [2, 1, 3, 4, 5],
 [1, 3, 2, 4, 5],
 [1, 2, 4, 3, 5],
 [1, 2, 3, 5, 4]]

Elements of given depth iterator:

sage: sorted(R.elements_of_depth_iterator(9))
[[4, 5, 3, 2, 1], [5, 3, 4, 2, 1], [5, 4, 2, 3, 1], [5, 4, 3, 1, 2]]
sage: list(R.elements_of_depth_iterator(10))
[[5, 4, 3, 2, 1]]

>>> from sage.all import *
>>> sorted(R.elements_of_depth_iterator(Integer(9)))
[[4, 5, 3, 2, 1], [5, 3, 4, 2, 1], [5, 4, 2, 3, 1], [5, 4, 3, 1, 2]]
>>> list(R.elements_of_depth_iterator(Integer(10)))
[[5, 4, 3, 2, 1]]

Graded components (set of elements of the same depth):

sage: # needs sage.combinat
sage: sorted(R.graded_component(0))
[[1, 2, 3, 4, 5]]
sage: sorted(R.graded_component(1))
[[1, 2, 3, 5, 4], [1, 2, 4, 3, 5], [1, 3, 2, 4, 5], [2, 1, 3, 4, 5]]
sage: sorted(R.graded_component(9))
[[4, 5, 3, 2, 1], [5, 3, 4, 2, 1], [5, 4, 2, 3, 1], [5, 4, 3, 1, 2]]
sage: sorted(R.graded_component(10))
[[5, 4, 3, 2, 1]]

>>> from sage.all import *
>>> # needs sage.combinat
>>> sorted(R.graded_component(Integer(0)))
[[1, 2, 3, 4, 5]]
>>> sorted(R.graded_component(Integer(1)))
[[1, 2, 3, 5, 4], [1, 2, 4, 3, 5], [1, 3, 2, 4, 5], [2, 1, 3, 4, 5]]
>>> sorted(R.graded_component(Integer(9)))
[[4, 5, 3, 2, 1], [5, 3, 4, 2, 1], [5, 4, 2, 3, 1], [5, 4, 3, 1, 2]]
>>> sorted(R.graded_component(Integer(10)))
[[5, 4, 3, 2, 1]]

Forest structure (Example 1)

The set of words over the alphabet \(\{a,b\}\) can be generated from the empty word by appending the letter \(a\) or \(b\) as a successor function. This set has a forest structure:

sage: seeds = ['']
sage: succ = lambda w: [w+'a', w+'b']
sage: C = RecursivelyEnumeratedSet(seeds, succ, structure='forest')
sage: C
An enumerated set with a forest structure

>>> from sage.all import *
>>> seeds = ['']
>>> succ = lambda w: [w+'a', w+'b']
>>> C = RecursivelyEnumeratedSet(seeds, succ, structure='forest')
>>> C
An enumerated set with a forest structure

Depth first search iterator:

sage: it = C.depth_first_search_iterator()
sage: [next(it) for _ in range(6)]
['', 'a', 'aa', 'aaa', 'aaaa', 'aaaaa']

>>> from sage.all import *
>>> it = C.depth_first_search_iterator()
>>> [next(it) for _ in range(Integer(6))]
['', 'a', 'aa', 'aaa', 'aaaa', 'aaaaa']

Breadth first search iterator:

sage: it = C.breadth_first_search_iterator()
sage: [next(it) for _ in range(6)]
['', 'a', 'b', 'aa', 'ab', 'ba']

>>> from sage.all import *
>>> it = C.breadth_first_search_iterator()
>>> [next(it) for _ in range(Integer(6))]
['', 'a', 'b', 'aa', 'ab', 'ba']

This example was provided by Florent Hivert.

How to define a set using those classes?

Only two things are necessary to define a set using a RecursivelyEnumeratedSet object (the other classes being very similar):

\[\begin{split}\begin{array}{ccc} & \emptyset \\ \hfil\swarrow & \downarrow & \searrow\hfil\\ a & b & c \\ \begin{array}{ccc} \swarrow & \downarrow & \searrow \\ aa & ab & ac \\ \end{array} & \begin{array}{ccc} \swarrow & \downarrow & \searrow \\ ba & bb & bc \\ \end{array} & \begin{array}{ccc} \swarrow & \downarrow & \searrow \\ ca & cb & cc \\ \end{array} \end{array}\end{split}\]

For the previous example, the two necessary pieces of information are:

  • the initial element "";

  • the function:

    lambda x: [x + letter for letter in ['a', 'b', 'c']

This would actually describe an infinite set, as such rules describe “all words” on 3 letters. Hence, it is a good idea to replace the function by:

lambda x: [x + letter for letter in ['a', 'b', 'c']] if len(x) < 2 else []

or even:

sage: def children(x):
....:     if len(x) < 2:
....:         for letter in ['a', 'b', 'c']:
....:             yield x+letter

>>> from sage.all import *
>>> def children(x):
...     if len(x) < Integer(2):
...         for letter in ['a', 'b', 'c']:
...             yield x+letter

We can then create the RecursivelyEnumeratedSet object with either:

sage: S = RecursivelyEnumeratedSet([''],
....:     lambda x: [x + letter for letter in ['a', 'b', 'c']]
....:               if len(x) < 2 else [],
....:     structure='forest', enumeration='depth',
....:     category=FiniteEnumeratedSets())
sage: S.list()
['', 'a', 'aa', 'ab', 'ac', 'b', 'ba', 'bb', 'bc', 'c', 'ca', 'cb', 'cc']

>>> from sage.all import *
>>> S = RecursivelyEnumeratedSet([''],
...     lambda x: [x + letter for letter in ['a', 'b', 'c']]
...               if len(x) < Integer(2) else [],
...     structure='forest', enumeration='depth',
...     category=FiniteEnumeratedSets())
>>> S.list()
['', 'a', 'aa', 'ab', 'ac', 'b', 'ba', 'bb', 'bc', 'c', 'ca', 'cb', 'cc']

or:

sage: S = RecursivelyEnumeratedSet([''], children,
....:     structure='forest', enumeration='depth',
....:     category=FiniteEnumeratedSets())
sage: S.list()
['', 'a', 'aa', 'ab', 'ac', 'b', 'ba', 'bb', 'bc', 'c', 'ca', 'cb', 'cc']

>>> from sage.all import *
>>> S = RecursivelyEnumeratedSet([''], children,
...     structure='forest', enumeration='depth',
...     category=FiniteEnumeratedSets())
>>> S.list()
['', 'a', 'aa', 'ab', 'ac', 'b', 'ba', 'bb', 'bc', 'c', 'ca', 'cb', 'cc']

Forest structure (Example 2)

This example was provided by Florent Hivert.

Here is a little more involved example. We want to iterate through all permutations of a given set \(S\). One solution is to take elements of \(S\) one by one and insert them at every position. So a node of the generating tree contains two pieces of information:

  • the list lst of already inserted element;

  • the set st of the yet to be inserted element.

We want to generate a permutation only if st is empty (leaves on the tree). Also suppose for the sake of the example, that instead of list we want to generate tuples. This selection of some nodes and final mapping of a function to the element is done by the post_process = f argument. The convention is that the generated elements are the s := f(n), except when s not None when no element is generated at all. Here is the code:

sage: def children(node):
....:     (lst, st) = node
....:     st = set(st) # make a copy
....:     if st:
....:        el = st.pop()
....:        for i in range(len(lst) + 1):
....:            yield (lst[0:i] + [el] + lst[i:], st)
sage: list(children(([1,2], {3,7,9})))
[([9, 1, 2], {3, 7}), ([1, 9, 2], {3, 7}), ([1, 2, 9], {3, 7})]
sage: def post_process(node):
....:     (l, s) = node
....:     return tuple(l) if not s else None
sage: S = RecursivelyEnumeratedSet( [([], {1,3,6,8})],
....:     children, post_process=post_process,
....:     structure='forest', enumeration='depth',
....:     category=FiniteEnumeratedSets())
sage: S.list()
[(6, 3, 1, 8), (3, 6, 1, 8), (3, 1, 6, 8), (3, 1, 8, 6), (6, 1, 3, 8),
 (1, 6, 3, 8), (1, 3, 6, 8), (1, 3, 8, 6), (6, 1, 8, 3), (1, 6, 8, 3),
 (1, 8, 6, 3), (1, 8, 3, 6), (6, 3, 8, 1), (3, 6, 8, 1), (3, 8, 6, 1),
 (3, 8, 1, 6), (6, 8, 3, 1), (8, 6, 3, 1), (8, 3, 6, 1), (8, 3, 1, 6),
 (6, 8, 1, 3), (8, 6, 1, 3), (8, 1, 6, 3), (8, 1, 3, 6)]
sage: S.cardinality()
24

>>> from sage.all import *
>>> def children(node):
...     (lst, st) = node
...     st = set(st) # make a copy
...     if st:
...        el = st.pop()
...        for i in range(len(lst) + Integer(1)):
...            yield (lst[Integer(0):i] + [el] + lst[i:], st)
>>> list(children(([Integer(1),Integer(2)], {Integer(3),Integer(7),Integer(9)})))
[([9, 1, 2], {3, 7}), ([1, 9, 2], {3, 7}), ([1, 2, 9], {3, 7})]
>>> def post_process(node):
...     (l, s) = node
...     return tuple(l) if not s else None
>>> S = RecursivelyEnumeratedSet( [([], {Integer(1),Integer(3),Integer(6),Integer(8)})],
...     children, post_process=post_process,
...     structure='forest', enumeration='depth',
...     category=FiniteEnumeratedSets())
>>> S.list()
[(6, 3, 1, 8), (3, 6, 1, 8), (3, 1, 6, 8), (3, 1, 8, 6), (6, 1, 3, 8),
 (1, 6, 3, 8), (1, 3, 6, 8), (1, 3, 8, 6), (6, 1, 8, 3), (1, 6, 8, 3),
 (1, 8, 6, 3), (1, 8, 3, 6), (6, 3, 8, 1), (3, 6, 8, 1), (3, 8, 6, 1),
 (3, 8, 1, 6), (6, 8, 3, 1), (8, 6, 3, 1), (8, 3, 6, 1), (8, 3, 1, 6),
 (6, 8, 1, 3), (8, 6, 1, 3), (8, 1, 6, 3), (8, 1, 3, 6)]
>>> S.cardinality()
24
sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet(seeds, successors, structure=None, enumeration=None, max_depth=None, post_process=None, facade=None, category=None)[source]

Return a recursively enumerated set.

A set \(S\) is called recursively enumerable if there is an algorithm that enumerates the members of \(S\). We consider here the recursively enumerated sets that are described by some seeds and a successor function successors.

Let \(U\) be a set and successors \(:U \to 2^U\) be a successor function associating to each element of \(U\) a subset of \(U\). Let seeds be a subset of \(U\). Let \(S\subseteq U\) be the set of elements of \(U\) that can be reached from a seed by applying recursively the successors function. This class provides different kinds of iterators (breadth first, depth first, elements of given depth, etc.) for the elements of \(S\).

See Wikipedia article Recursively_enumerable_set.

INPUT:

  • seeds – list (or iterable) of hashable objects

  • successors – function (or callable) returning a list (or iterable) of hashable objects

  • structure – string (default: None); structure of the set, possible values are:

    • None – nothing is known about the structure of the set

    • 'forest' – if the successors function generates a forest, that is, each element can be reached uniquely from a seed

    • 'graded' – if the successors function is graded, that is, all paths from a seed to a given element have equal length

    • 'symmetric' – if the relation is symmetric, that is, y in successors(x) if and only if x in successors(y)

  • enumeration – 'depth', 'breadth', 'naive' or None (default: None); the default enumeration for the __iter__ function

  • max_depth – integer (default: float("inf")); limit the search to a certain depth, currently works only for breadth first search

  • post_process – (default: None) for forest only

  • facade – (default: None)

  • category – (default: None)

EXAMPLES:

A recursive set with no other information:

sage: f = lambda a: [a+3, a+5]
sage: C = RecursivelyEnumeratedSet([0], f)
sage: C
A recursively enumerated set (breadth first search)
sage: it = iter(C)
sage: [next(it) for _ in range(10)]
[0, 3, 5, 6, 8, 10, 9, 11, 13, 15]

>>> from sage.all import *
>>> f = lambda a: [a+Integer(3), a+Integer(5)]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f)
>>> C
A recursively enumerated set (breadth first search)
>>> it = iter(C)
>>> [next(it) for _ in range(Integer(10))]
[0, 3, 5, 6, 8, 10, 9, 11, 13, 15]

A recursive set with a forest structure:

sage: f = lambda a: [2*a,2*a+1]
sage: C = RecursivelyEnumeratedSet([1], f, structure='forest'); C
An enumerated set with a forest structure
sage: it = C.depth_first_search_iterator()
sage: [next(it) for _ in range(7)]
[1, 2, 4, 8, 16, 32, 64]
sage: it = C.breadth_first_search_iterator()
sage: [next(it) for _ in range(7)]
[1, 2, 3, 4, 5, 6, 7]

>>> from sage.all import *
>>> f = lambda a: [Integer(2)*a,Integer(2)*a+Integer(1)]
>>> C = RecursivelyEnumeratedSet([Integer(1)], f, structure='forest'); C
An enumerated set with a forest structure
>>> it = C.depth_first_search_iterator()
>>> [next(it) for _ in range(Integer(7))]
[1, 2, 4, 8, 16, 32, 64]
>>> it = C.breadth_first_search_iterator()
>>> [next(it) for _ in range(Integer(7))]
[1, 2, 3, 4, 5, 6, 7]

A recursive set given by a symmetric relation:

sage: f = lambda a: [a-1,a+1]
sage: C = RecursivelyEnumeratedSet([10, 15], f, structure='symmetric')
sage: C
A recursively enumerated set with a symmetric structure (breadth first search)
sage: it = iter(C)
sage: [next(it) for _ in range(7)]
[10, 15, 9, 11, 14, 16, 8]

>>> from sage.all import *
>>> f = lambda a: [a-Integer(1),a+Integer(1)]
>>> C = RecursivelyEnumeratedSet([Integer(10), Integer(15)], f, structure='symmetric')
>>> C
A recursively enumerated set with a symmetric structure (breadth first search)
>>> it = iter(C)
>>> [next(it) for _ in range(Integer(7))]
[10, 15, 9, 11, 14, 16, 8]

A recursive set given by a graded relation:

sage: # needs sage.symbolic
sage: def f(a):
....:     return [a + 1, a + I]
sage: C = RecursivelyEnumeratedSet([0], f, structure='graded'); C
A recursively enumerated set with a graded structure (breadth first search)
sage: it = iter(C)
sage: [next(it) for _ in range(7)]
[0, 1, I, 2, I + 1, 2*I, 3]

>>> from sage.all import *
>>> # needs sage.symbolic
>>> def f(a):
...     return [a + Integer(1), a + I]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f, structure='graded'); C
A recursively enumerated set with a graded structure (breadth first search)
>>> it = iter(C)
>>> [next(it) for _ in range(Integer(7))]
[0, 1, I, 2, I + 1, 2*I, 3]

Warning

If you do not set a good structure, you might obtain bad results, like elements generated twice:

sage: f = lambda a: [a-1,a+1]
sage: C = RecursivelyEnumeratedSet([0], f, structure='graded')
sage: it = iter(C)
sage: [next(it) for _ in range(7)]
[0, -1, 1, -2, 0, 2, -3]

>>> from sage.all import *
>>> f = lambda a: [a-Integer(1),a+Integer(1)]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f, structure='graded')
>>> it = iter(C)
>>> [next(it) for _ in range(Integer(7))]
[0, -1, 1, -2, 0, 2, -3]
class sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_forest(roots=None, children=None, post_process=None, algorithm='depth', facade=None, category=None)[source]

Bases: Parent

The enumerated set of the nodes of the forest having the given roots, and where children(x) returns the children of the node x of the forest.

See also sage.combinat.backtrack.GenericBacktracker, RecursivelyEnumeratedSet_graded, and RecursivelyEnumeratedSet_symmetric.

INPUT:

  • roots – list (or iterable)

  • children – a function returning a list (or iterable, or iterator)

  • post_process – a function defined over the nodes of the forest (default: no post processing)

  • algorithm – 'depth' or 'breadth' (default: 'depth')

  • category – a category (default: EnumeratedSets)

The option post_process allows for customizing the nodes that are actually produced. Furthermore, if f(x) returns None, then x won’t be output at all.

EXAMPLES:

We construct the set of all binary sequences of length at most three, and list them:

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: S = RecursivelyEnumeratedSet_forest( [[]],
....:     lambda l: [l + [0], l + [1]] if len(l) < 3 else [],
....:     category=FiniteEnumeratedSets())
sage: S.list()
[[],
 [0], [0, 0], [0, 0, 0], [0, 0, 1], [0, 1], [0, 1, 0], [0, 1, 1],
 [1], [1, 0], [1, 0, 0], [1, 0, 1], [1, 1], [1, 1, 0], [1, 1, 1]]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> S = RecursivelyEnumeratedSet_forest( [[]],
...     lambda l: [l + [Integer(0)], l + [Integer(1)]] if len(l) < Integer(3) else [],
...     category=FiniteEnumeratedSets())
>>> S.list()
[[],
 [0], [0, 0], [0, 0, 0], [0, 0, 1], [0, 1], [0, 1, 0], [0, 1, 1],
 [1], [1, 0], [1, 0, 0], [1, 0, 1], [1, 1], [1, 1, 0], [1, 1, 1]]

RecursivelyEnumeratedSet_forest needs to be explicitly told that the set is finite for the following to work:

sage: S.category()
Category of finite enumerated sets
sage: S.cardinality()
15

>>> from sage.all import *
>>> S.category()
Category of finite enumerated sets
>>> S.cardinality()
15

We proceed with the set of all lists of letters in 0,1,2 without repetitions, ordered by increasing length (i.e. using a breadth first search through the tree):

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: tb = RecursivelyEnumeratedSet_forest( [[]],
....:       lambda l: [l + [i] for i in range(3) if i not in l],
....:       algorithm = 'breadth',
....:       category=FiniteEnumeratedSets())
sage: tb[0]
[]
sage: tb.cardinality()
16
sage: list(tb)
[[],
 [0], [1], [2],
 [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1],
 [0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> tb = RecursivelyEnumeratedSet_forest( [[]],
...       lambda l: [l + [i] for i in range(Integer(3)) if i not in l],
...       algorithm = 'breadth',
...       category=FiniteEnumeratedSets())
>>> tb[Integer(0)]
[]
>>> tb.cardinality()
16
>>> list(tb)
[[],
 [0], [1], [2],
 [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1],
 [0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

For infinite sets, this option should be set carefully to ensure that all elements are actually generated. The following example builds the set of all ordered pairs \((i,j)\) of nonnegative integers such that \(j\leq 1\):

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: I = RecursivelyEnumeratedSet_forest([(0,0)],
....:                  lambda l: [(l[0]+1, l[1]), (l[0], 1)]
....:                            if l[1] == 0 else [(l[0], l[1]+1)])

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> I = RecursivelyEnumeratedSet_forest([(Integer(0),Integer(0))],
...                  lambda l: [(l[Integer(0)]+Integer(1), l[Integer(1)]), (l[Integer(0)], Integer(1))]
...                            if l[Integer(1)] == Integer(0) else [(l[Integer(0)], l[Integer(1)]+Integer(1))])

With a depth first search, only the elements of the form \((i,0)\) are generated:

sage: depth_search = I.depth_first_search_iterator()
sage: [next(depth_search) for i in range(7)]
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0)]

>>> from sage.all import *
>>> depth_search = I.depth_first_search_iterator()
>>> [next(depth_search) for i in range(Integer(7))]
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0)]

Using instead breadth first search gives the usual anti-diagonal iterator:

sage: breadth_search = I.breadth_first_search_iterator()
sage: [next(breadth_search) for i in range(15)]
[(0, 0),
 (1, 0), (0, 1),
 (2, 0), (1, 1), (0, 2),
 (3, 0), (2, 1), (1, 2), (0, 3),
 (4, 0), (3, 1), (2, 2), (1, 3), (0, 4)]

>>> from sage.all import *
>>> breadth_search = I.breadth_first_search_iterator()
>>> [next(breadth_search) for i in range(Integer(15))]
[(0, 0),
 (1, 0), (0, 1),
 (2, 0), (1, 1), (0, 2),
 (3, 0), (2, 1), (1, 2), (0, 3),
 (4, 0), (3, 1), (2, 2), (1, 3), (0, 4)]

Deriving subclasses

The class of a parent \(A\) may derive from RecursivelyEnumeratedSet_forest so that \(A\) can benefit from enumeration tools. As a running example, we consider the problem of enumerating integers whose binary expansion have at most three nonzero digits. For example, \(3 = 2^1 + 2^0\) has two nonzero digits. \(15 = 2^3 + 2^2 + 2^1 + 2^0\) has four nonzero digits. In fact, \(15\) is the smallest integer which is not in the enumerated set.

To achieve this, we use RecursivelyEnumeratedSet_forest to enumerate binary tuples with at most three nonzero digits, apply a post processing to recover the corresponding integers, and discard tuples finishing by zero.

A first approach is to pass the roots and children functions as arguments to RecursivelyEnumeratedSet_forest.__init__():

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: class A(UniqueRepresentation, RecursivelyEnumeratedSet_forest):
....:     def __init__(self):
....:         RecursivelyEnumeratedSet_forest.__init__(self, [()],
....:             lambda x: [x + (0,), x + (1,)] if sum(x) < 3 else [],
....:             lambda x: sum(x[i]*2^i for i in range(len(x)))
....:                           if sum(x) != 0 and x[-1] != 0 else None,
....:             algorithm='breadth',
....:             category=InfiniteEnumeratedSets())
sage: MyForest = A(); MyForest
An enumerated set with a forest structure
sage: MyForest.category()
Category of infinite enumerated sets
sage: p = iter(MyForest)
sage: [next(p) for i in range(30)]
[1, 2, 3, 4, 6, 5, 7, 8, 12, 10, 14, 9, 13, 11, 16, 24,
 20, 28, 18, 26, 22, 17, 25, 21, 19, 32, 48, 40, 56, 36]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> class A(UniqueRepresentation, RecursivelyEnumeratedSet_forest):
...     def __init__(self):
...         RecursivelyEnumeratedSet_forest.__init__(self, [()],
...             lambda x: [x + (Integer(0),), x + (Integer(1),)] if sum(x) < Integer(3) else [],
...             lambda x: sum(x[i]*Integer(2)**i for i in range(len(x)))
...                           if sum(x) != Integer(0) and x[-Integer(1)] != Integer(0) else None,
...             algorithm='breadth',
...             category=InfiniteEnumeratedSets())
>>> MyForest = A(); MyForest
An enumerated set with a forest structure
>>> MyForest.category()
Category of infinite enumerated sets
>>> p = iter(MyForest)
>>> [next(p) for i in range(Integer(30))]
[1, 2, 3, 4, 6, 5, 7, 8, 12, 10, 14, 9, 13, 11, 16, 24,
 20, 28, 18, 26, 22, 17, 25, 21, 19, 32, 48, 40, 56, 36]

An alternative approach is to implement roots and children as methods of the subclass (in fact they could also be attributes of \(A\)). Namely, A.roots() must return an iterable containing the enumeration generators, and A.children(x) must return an iterable over the children of \(x\). Optionally, \(A\) can have a method or attribute such that A.post_process(x) returns the desired output for the node x of the tree:

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: class A(UniqueRepresentation, RecursivelyEnumeratedSet_forest):
....:     def __init__(self):
....:         RecursivelyEnumeratedSet_forest.__init__(self, algorithm='breadth',
....:                               category=InfiniteEnumeratedSets())
....:     def roots(self):
....:         return [()]
....:     def children(self, x):
....:         if sum(x) < 3:
....:             return [x + (0,), x + (1,)]
....:         else:
....:             return []
....:     def post_process(self, x):
....:         if sum(x) == 0 or x[-1] == 0:
....:             return None
....:         else:
....:             return sum(x[i]*2^i for i in range(len(x)))
sage: MyForest = A(); MyForest
An enumerated set with a forest structure
sage: MyForest.category()
Category of infinite enumerated sets
sage: p = iter(MyForest)
sage: [next(p) for i in range(30)]
[1, 2, 3, 4, 6, 5, 7, 8, 12, 10, 14, 9, 13, 11, 16, 24,
 20, 28, 18, 26, 22, 17, 25, 21, 19, 32, 48, 40, 56, 36]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> class A(UniqueRepresentation, RecursivelyEnumeratedSet_forest):
...     def __init__(self):
...         RecursivelyEnumeratedSet_forest.__init__(self, algorithm='breadth',
...                               category=InfiniteEnumeratedSets())
...     def roots(self):
...         return [()]
...     def children(self, x):
...         if sum(x) < Integer(3):
...             return [x + (Integer(0),), x + (Integer(1),)]
...         else:
...             return []
...     def post_process(self, x):
...         if sum(x) == Integer(0) or x[-Integer(1)] == Integer(0):
...             return None
...         else:
...             return sum(x[i]*Integer(2)**i for i in range(len(x)))
>>> MyForest = A(); MyForest
An enumerated set with a forest structure
>>> MyForest.category()
Category of infinite enumerated sets
>>> p = iter(MyForest)
>>> [next(p) for i in range(Integer(30))]
[1, 2, 3, 4, 6, 5, 7, 8, 12, 10, 14, 9, 13, 11, 16, 24,
 20, 28, 18, 26, 22, 17, 25, 21, 19, 32, 48, 40, 56, 36]

Warning

A RecursivelyEnumeratedSet_forest instance is picklable if and only if the input functions are themselves picklable. This excludes anonymous or interactively defined functions:

sage: def children(x):
....:     return [x + 1]
sage: S = RecursivelyEnumeratedSet_forest([1], children, category=InfiniteEnumeratedSets())
sage: dumps(S)
Traceback (most recent call last):
...
PicklingError: Can't pickle <...function...>: attribute lookup ... failed

>>> from sage.all import *
>>> def children(x):
...     return [x + Integer(1)]
>>> S = RecursivelyEnumeratedSet_forest([Integer(1)], children, category=InfiniteEnumeratedSets())
>>> dumps(S)
Traceback (most recent call last):
...
PicklingError: Can't pickle <...function...>: attribute lookup ... failed

Let us now fake children being defined in a Python module:

sage: import __main__
sage: __main__.children = children
sage: S = RecursivelyEnumeratedSet_forest([1], children, category=InfiniteEnumeratedSets())
sage: loads(dumps(S))
An enumerated set with a forest structure

>>> from sage.all import *
>>> import __main__
>>> __main__.children = children
>>> S = RecursivelyEnumeratedSet_forest([Integer(1)], children, category=InfiniteEnumeratedSets())
>>> loads(dumps(S))
An enumerated set with a forest structure
breadth_first_search_iterator()[source]

Return a breadth first search iterator over the elements of self.

EXAMPLES:

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: f = RecursivelyEnumeratedSet_forest([[]],
....:                  lambda l: [l+[0], l+[1]] if len(l) < 3 else [])
sage: list(f.breadth_first_search_iterator())
[[], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
sage: S = RecursivelyEnumeratedSet_forest([(0,0)],
....: lambda x : [(x[0], x[1]+1)] if x[1] != 0 else [(x[0]+1,0), (x[0],1)],
....: post_process = lambda x: x if ((is_prime(x[0]) and is_prime(x[1])) and ((x[0] - x[1]) == 2)) else None)
sage: p = S.breadth_first_search_iterator()
sage: [next(p), next(p), next(p), next(p), next(p), next(p), next(p)]
[(5, 3), (7, 5), (13, 11), (19, 17), (31, 29), (43, 41), (61, 59)]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> f = RecursivelyEnumeratedSet_forest([[]],
...                  lambda l: [l+[Integer(0)], l+[Integer(1)]] if len(l) < Integer(3) else [])
>>> list(f.breadth_first_search_iterator())
[[], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
>>> S = RecursivelyEnumeratedSet_forest([(Integer(0),Integer(0))],
... lambda x : [(x[Integer(0)], x[Integer(1)]+Integer(1))] if x[Integer(1)] != Integer(0) else [(x[Integer(0)]+Integer(1),Integer(0)), (x[Integer(0)],Integer(1))],
... post_process = lambda x: x if ((is_prime(x[Integer(0)]) and is_prime(x[Integer(1)])) and ((x[Integer(0)] - x[Integer(1)]) == Integer(2))) else None)
>>> p = S.breadth_first_search_iterator()
>>> [next(p), next(p), next(p), next(p), next(p), next(p), next(p)]
[(5, 3), (7, 5), (13, 11), (19, 17), (31, 29), (43, 41), (61, 59)]
children(x)[source]

Return the children of the element x.

The result can be a list, an iterable, an iterator, or even a generator.

EXAMPLES:

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: I = RecursivelyEnumeratedSet_forest([(0,0)], lambda l: [(l[0]+1, l[1]), (l[0], 1)] if l[1] == 0 else [(l[0], l[1]+1)])
sage: [i for i in I.children((0,0))]
[(1, 0), (0, 1)]
sage: [i for i in I.children((1,0))]
[(2, 0), (1, 1)]
sage: [i for i in I.children((1,1))]
[(1, 2)]
sage: [i for i in I.children((4,1))]
[(4, 2)]
sage: [i for i in I.children((4,0))]
[(5, 0), (4, 1)]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> I = RecursivelyEnumeratedSet_forest([(Integer(0),Integer(0))], lambda l: [(l[Integer(0)]+Integer(1), l[Integer(1)]), (l[Integer(0)], Integer(1))] if l[Integer(1)] == Integer(0) else [(l[Integer(0)], l[Integer(1)]+Integer(1))])
>>> [i for i in I.children((Integer(0),Integer(0)))]
[(1, 0), (0, 1)]
>>> [i for i in I.children((Integer(1),Integer(0)))]
[(2, 0), (1, 1)]
>>> [i for i in I.children((Integer(1),Integer(1)))]
[(1, 2)]
>>> [i for i in I.children((Integer(4),Integer(1)))]
[(4, 2)]
>>> [i for i in I.children((Integer(4),Integer(0)))]
[(5, 0), (4, 1)]
depth_first_search_iterator()[source]

Return a depth first search iterator over the elements of self.

EXAMPLES:

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: f = RecursivelyEnumeratedSet_forest([[]],
....:                  lambda l: [l + [0], l + [1]] if len(l) < 3 else [])
sage: list(f.depth_first_search_iterator())
[[], [0], [0, 0], [0, 0, 0], [0, 0, 1], [0, 1], [0, 1, 0], [0, 1, 1],
     [1], [1, 0], [1, 0, 0], [1, 0, 1], [1, 1], [1, 1, 0], [1, 1, 1]]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> f = RecursivelyEnumeratedSet_forest([[]],
...                  lambda l: [l + [Integer(0)], l + [Integer(1)]] if len(l) < Integer(3) else [])
>>> list(f.depth_first_search_iterator())
[[], [0], [0, 0], [0, 0, 0], [0, 0, 1], [0, 1], [0, 1, 0], [0, 1, 1],
     [1], [1, 0], [1, 0, 0], [1, 0, 1], [1, 1], [1, 1, 0], [1, 1, 1]]
elements_of_depth_iterator(depth=0)[source]

Return an iterator over the elements of self of given depth. An element of depth \(n\) can be obtained by applying the children function \(n\) times from a root.

EXAMPLES:

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: S = RecursivelyEnumeratedSet_forest([(0,0)] ,
....:        lambda x : [(x[0], x[1]+1)] if x[1] != 0 else [(x[0]+1,0), (x[0],1)],
....:        post_process = lambda x: x if ((is_prime(x[0]) and is_prime(x[1]))
....:                                        and ((x[0] - x[1]) == 2)) else None)
sage: p = S.elements_of_depth_iterator(8)
sage: next(p)
(5, 3)
sage: S = RecursivelyEnumeratedSet_forest(NN, lambda x : [],
....:                      lambda x: x^2 if x.is_prime() else None)
sage: p = S.elements_of_depth_iterator(0)
sage: [next(p), next(p), next(p), next(p), next(p)]
[4, 9, 25, 49, 121]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> S = RecursivelyEnumeratedSet_forest([(Integer(0),Integer(0))] ,
...        lambda x : [(x[Integer(0)], x[Integer(1)]+Integer(1))] if x[Integer(1)] != Integer(0) else [(x[Integer(0)]+Integer(1),Integer(0)), (x[Integer(0)],Integer(1))],
...        post_process = lambda x: x if ((is_prime(x[Integer(0)]) and is_prime(x[Integer(1)]))
...                                        and ((x[Integer(0)] - x[Integer(1)]) == Integer(2))) else None)
>>> p = S.elements_of_depth_iterator(Integer(8))
>>> next(p)
(5, 3)
>>> S = RecursivelyEnumeratedSet_forest(NN, lambda x : [],
...                      lambda x: x**Integer(2) if x.is_prime() else None)
>>> p = S.elements_of_depth_iterator(Integer(0))
>>> [next(p), next(p), next(p), next(p), next(p)]
[4, 9, 25, 49, 121]
map_reduce(map_function=None, reduce_function=None, reduce_init=None)[source]

Apply a Map/Reduce algorithm on self.

INPUT:

  • map_function – a function from the element of self to some set with a reduce operation (e.g.: a monoid). The default value is the constant function 1.

  • reduce_function – the reduce function (e.g.: the addition of a monoid); the default value is +

  • reduce_init – the initialisation of the reduction (e.g.: the neutral element of the monoid); the default value is 0

Note

the effect of the default values is to compute the cardinality of self.

EXAMPLES:

sage: seeds = [([i], i, i) for i in range(1, 10)]
sage: def succ(t):
....:     list, sum, last = t
....:     return [(list + [i], sum + i, i) for i in range(1, last)]
sage: F = RecursivelyEnumeratedSet(seeds, succ,
....:         structure='forest', enumeration='depth')

sage: # needs sage.symbolic
sage: y = var('y')
sage: def map_function(t):
....:     li, sum, _ = t
....:     return y ^ sum
sage: def reduce_function(x, y):
....:     return x + y
sage: F.map_reduce(map_function, reduce_function, 0)
y^45 + y^44 + y^43 + 2*y^42 + 2*y^41 + 3*y^40 + 4*y^39 + 5*y^38 + 6*y^37
+ 8*y^36 + 9*y^35 + 10*y^34 + 12*y^33 + 13*y^32 + 15*y^31 + 17*y^30
+ 18*y^29 + 19*y^28 + 21*y^27 + 21*y^26 + 22*y^25 + 23*y^24 + 23*y^23
+ 23*y^22 + 23*y^21 + 22*y^20 + 21*y^19 + 21*y^18 + 19*y^17 + 18*y^16
+ 17*y^15 + 15*y^14 + 13*y^13 + 12*y^12 + 10*y^11 + 9*y^10 + 8*y^9 + 6*y^8
+ 5*y^7 + 4*y^6 + 3*y^5 + 2*y^4 + 2*y^3 + y^2 + y

>>> from sage.all import *
>>> seeds = [([i], i, i) for i in range(Integer(1), Integer(10))]
>>> def succ(t):
...     list, sum, last = t
...     return [(list + [i], sum + i, i) for i in range(Integer(1), last)]
>>> F = RecursivelyEnumeratedSet(seeds, succ,
...         structure='forest', enumeration='depth')

>>> # needs sage.symbolic
>>> y = var('y')
>>> def map_function(t):
...     li, sum, _ = t
...     return y ** sum
>>> def reduce_function(x, y):
...     return x + y
>>> F.map_reduce(map_function, reduce_function, Integer(0))
y^45 + y^44 + y^43 + 2*y^42 + 2*y^41 + 3*y^40 + 4*y^39 + 5*y^38 + 6*y^37
+ 8*y^36 + 9*y^35 + 10*y^34 + 12*y^33 + 13*y^32 + 15*y^31 + 17*y^30
+ 18*y^29 + 19*y^28 + 21*y^27 + 21*y^26 + 22*y^25 + 23*y^24 + 23*y^23
+ 23*y^22 + 23*y^21 + 22*y^20 + 21*y^19 + 21*y^18 + 19*y^17 + 18*y^16
+ 17*y^15 + 15*y^14 + 13*y^13 + 12*y^12 + 10*y^11 + 9*y^10 + 8*y^9 + 6*y^8
+ 5*y^7 + 4*y^6 + 3*y^5 + 2*y^4 + 2*y^3 + y^2 + y

Here is an example with the default values:

sage: F.map_reduce()
511

>>> from sage.all import *
>>> F.map_reduce()
511

See also

sage.parallel.map_reduce

roots()[source]

Return an iterable over the roots of self.

EXAMPLES:

sage: from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
sage: I = RecursivelyEnumeratedSet_forest([(0,0)], lambda l: [(l[0]+1, l[1]), (l[0], 1)] if l[1] == 0 else [(l[0], l[1]+1)])
sage: [i for i in I.roots()]
[(0, 0)]
sage: I = RecursivelyEnumeratedSet_forest([(0,0),(1,1)], lambda l: [(l[0]+1, l[1]), (l[0], 1)] if l[1] == 0 else [(l[0], l[1]+1)])
sage: [i for i in I.roots()]
[(0, 0), (1, 1)]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet_forest
>>> I = RecursivelyEnumeratedSet_forest([(Integer(0),Integer(0))], lambda l: [(l[Integer(0)]+Integer(1), l[Integer(1)]), (l[Integer(0)], Integer(1))] if l[Integer(1)] == Integer(0) else [(l[Integer(0)], l[Integer(1)]+Integer(1))])
>>> [i for i in I.roots()]
[(0, 0)]
>>> I = RecursivelyEnumeratedSet_forest([(Integer(0),Integer(0)),(Integer(1),Integer(1))], lambda l: [(l[Integer(0)]+Integer(1), l[Integer(1)]), (l[Integer(0)], Integer(1))] if l[Integer(1)] == Integer(0) else [(l[Integer(0)], l[Integer(1)]+Integer(1))])
>>> [i for i in I.roots()]
[(0, 0), (1, 1)]
class sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic[source]

Bases: Parent

A generic recursively enumerated set.

For more information, see RecursivelyEnumeratedSet().

EXAMPLES:

sage: f = lambda a:[a+1]

>>> from sage.all import *
>>> f = lambda a:[a+Integer(1)]

Different structure for the sets:

sage: RecursivelyEnumeratedSet([0], f, structure=None)
A recursively enumerated set (breadth first search)
sage: RecursivelyEnumeratedSet([0], f, structure='graded')
A recursively enumerated set with a graded structure (breadth first search)
sage: RecursivelyEnumeratedSet([0], f, structure='symmetric')
A recursively enumerated set with a symmetric structure (breadth first search)
sage: RecursivelyEnumeratedSet([0], f, structure='forest')
An enumerated set with a forest structure

>>> from sage.all import *
>>> RecursivelyEnumeratedSet([Integer(0)], f, structure=None)
A recursively enumerated set (breadth first search)
>>> RecursivelyEnumeratedSet([Integer(0)], f, structure='graded')
A recursively enumerated set with a graded structure (breadth first search)
>>> RecursivelyEnumeratedSet([Integer(0)], f, structure='symmetric')
A recursively enumerated set with a symmetric structure (breadth first search)
>>> RecursivelyEnumeratedSet([Integer(0)], f, structure='forest')
An enumerated set with a forest structure

Different default enumeration algorithms:

sage: RecursivelyEnumeratedSet([0], f, enumeration='breadth')
A recursively enumerated set (breadth first search)
sage: RecursivelyEnumeratedSet([0], f, enumeration='naive')
A recursively enumerated set (naive search)
sage: RecursivelyEnumeratedSet([0], f, enumeration='depth')
A recursively enumerated set (depth first search)

>>> from sage.all import *
>>> RecursivelyEnumeratedSet([Integer(0)], f, enumeration='breadth')
A recursively enumerated set (breadth first search)
>>> RecursivelyEnumeratedSet([Integer(0)], f, enumeration='naive')
A recursively enumerated set (naive search)
>>> RecursivelyEnumeratedSet([Integer(0)], f, enumeration='depth')
A recursively enumerated set (depth first search)
breadth_first_search_iterator(max_depth=None)[source]

Iterate on the elements of self (breadth first).

This code remembers every element generated.

The elements are guaranteed to be enumerated in the order in which they are first visited (left-to-right traversal).

INPUT:

  • max_depth – (default: self._max_depth) specifies the maximal depth to which elements are computed

EXAMPLES:

sage: f = lambda a: [a+3, a+5]
sage: C = RecursivelyEnumeratedSet([0], f)
sage: it = C.breadth_first_search_iterator()
sage: [next(it) for _ in range(10)]
[0, 3, 5, 6, 8, 10, 9, 11, 13, 15]

>>> from sage.all import *
>>> f = lambda a: [a+Integer(3), a+Integer(5)]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f)
>>> it = C.breadth_first_search_iterator()
>>> [next(it) for _ in range(Integer(10))]
[0, 3, 5, 6, 8, 10, 9, 11, 13, 15]
depth_first_search_iterator()[source]

Iterate on the elements of self (depth first).

This code remembers every element generated.

The elements are traversed right-to-left, so the last element returned by the successor function is visited first.

See Wikipedia article Depth-first_search.

EXAMPLES:

sage: f = lambda a: [a+3, a+5]
sage: C = RecursivelyEnumeratedSet([0], f)
sage: it = C.depth_first_search_iterator()
sage: [next(it) for _ in range(10)]
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]

>>> from sage.all import *
>>> f = lambda a: [a+Integer(3), a+Integer(5)]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f)
>>> it = C.depth_first_search_iterator()
>>> [next(it) for _ in range(Integer(10))]
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]
elements_of_depth_iterator(depth)[source]

Iterate over the elements of self of given depth.

An element of depth \(n\) can be obtained by applying the successor function \(n\) times to a seed.

INPUT:

  • depth – integer

OUTPUT: an iterator

EXAMPLES:

sage: f = lambda a: [a-1, a+1]
sage: S = RecursivelyEnumeratedSet([5, 10], f, structure='symmetric')
sage: it = S.elements_of_depth_iterator(2)
sage: sorted(it)
[3, 7, 8, 12]

>>> from sage.all import *
>>> f = lambda a: [a-Integer(1), a+Integer(1)]
>>> S = RecursivelyEnumeratedSet([Integer(5), Integer(10)], f, structure='symmetric')
>>> it = S.elements_of_depth_iterator(Integer(2))
>>> sorted(it)
[3, 7, 8, 12]
graded_component(depth)[source]

Return the graded component of given depth.

This method caches each lower graded component.

A graded component is a set of elements of the same depth where the depth of an element is its minimal distance to a root.

It is currently implemented only for graded or symmetric structure.

INPUT:

  • depth – integer

OUTPUT: set

EXAMPLES:

sage: f = lambda a: [a+3, a+5]
sage: C = RecursivelyEnumeratedSet([0], f)
sage: C.graded_component(0)
Traceback (most recent call last):
...
NotImplementedError: graded_component_iterator method currently implemented only for graded or symmetric structure

>>> from sage.all import *
>>> f = lambda a: [a+Integer(3), a+Integer(5)]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f)
>>> C.graded_component(Integer(0))
Traceback (most recent call last):
...
NotImplementedError: graded_component_iterator method currently implemented only for graded or symmetric structure
graded_component_iterator()[source]

Iterate over the graded components of self.

A graded component is a set of elements of the same depth.

It is currently implemented only for graded or symmetric structure.

OUTPUT: an iterator of sets

EXAMPLES:

sage: f = lambda a: [a+3, a+5]
sage: C = RecursivelyEnumeratedSet([0], f)
sage: it = C.graded_component_iterator()    # todo: not implemented

>>> from sage.all import *
>>> f = lambda a: [a+Integer(3), a+Integer(5)]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f)
>>> it = C.graded_component_iterator()    # todo: not implemented
naive_search_iterator()[source]

Iterate on the elements of self (in no particular order).

This code remembers every element generated.

seeds()[source]

Return an iterable over the seeds of self.

EXAMPLES:

sage: R = RecursivelyEnumeratedSet([1], lambda x: [x + 1, x - 1])
sage: R.seeds()
[1]

>>> from sage.all import *
>>> R = RecursivelyEnumeratedSet([Integer(1)], lambda x: [x + Integer(1), x - Integer(1)])
>>> R.seeds()
[1]
successors[source]
to_digraph(max_depth=None, loops=True, multiedges=True)[source]

Return the directed graph of the recursively enumerated set.

INPUT:

  • max_depth – (default: self._max_depth) specifies the maximal depth for which outgoing edges of elements are computed

  • loops – boolean (default: True); option for the digraph

  • multiedges – boolean (default: True); option of the digraph

OUTPUT: a directed graph

Warning

If the set is infinite, this will loop forever unless max_depth is finite.

EXAMPLES:

sage: child = lambda i: [(i+3) % 10, (i+8) % 10]
sage: R = RecursivelyEnumeratedSet([0], child)
sage: R.to_digraph()                                                        # needs sage.graphs
Looped multi-digraph on 10 vertices

>>> from sage.all import *
>>> child = lambda i: [(i+Integer(3)) % Integer(10), (i+Integer(8)) % Integer(10)]
>>> R = RecursivelyEnumeratedSet([Integer(0)], child)
>>> R.to_digraph()                                                        # needs sage.graphs
Looped multi-digraph on 10 vertices

Digraph of a recursively enumerated set with a symmetric structure of infinite cardinality using max_depth argument:

sage: succ = lambda a: [(a[0]-1,a[1]), (a[0],a[1]-1), (a[0]+1,a[1]), (a[0],a[1]+1)]
sage: seeds = [(0,0)]
sage: C = RecursivelyEnumeratedSet(seeds, succ, structure='symmetric')
sage: C.to_digraph(max_depth=3)                                             # needs sage.graphs
Looped multi-digraph on 41 vertices

>>> from sage.all import *
>>> succ = lambda a: [(a[Integer(0)]-Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]-Integer(1)), (a[Integer(0)]+Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]+Integer(1))]
>>> seeds = [(Integer(0),Integer(0))]
>>> C = RecursivelyEnumeratedSet(seeds, succ, structure='symmetric')
>>> C.to_digraph(max_depth=Integer(3))                                             # needs sage.graphs
Looped multi-digraph on 41 vertices

The max_depth argument can be given at the creation of the set:

sage: C = RecursivelyEnumeratedSet(seeds, succ, structure='symmetric',
....:                              max_depth=2)
sage: C.to_digraph()                                                        # needs sage.graphs
Looped multi-digraph on 25 vertices

>>> from sage.all import *
>>> C = RecursivelyEnumeratedSet(seeds, succ, structure='symmetric',
...                              max_depth=Integer(2))
>>> C.to_digraph()                                                        # needs sage.graphs
Looped multi-digraph on 25 vertices

Digraph of a recursively enumerated set with a graded structure:

sage: f = lambda a: [a+1, a+I]
sage: C = RecursivelyEnumeratedSet([0], f, structure='graded')
sage: C.to_digraph(max_depth=4)                                             # needs sage.graphs
Looped multi-digraph on 21 vertices

>>> from sage.all import *
>>> f = lambda a: [a+Integer(1), a+I]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f, structure='graded')
>>> C.to_digraph(max_depth=Integer(4))                                             # needs sage.graphs
Looped multi-digraph on 21 vertices
class sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_graded[source]

Bases: RecursivelyEnumeratedSet_generic

Generic tool for constructing ideals of a graded relation.

INPUT:

  • seeds – list (or iterable) of hashable objects

  • successors – function (or callable) returning a list (or iterable)

  • enumeration – 'depth', 'breadth' or None (default: None)

  • max_depth – integer (default: float("inf"))

EXAMPLES:

sage: f = lambda a: [(a[0]+1,a[1]), (a[0],a[1]+1)]
sage: C = RecursivelyEnumeratedSet([(0,0)], f, structure='graded', max_depth=3)
sage: C
A recursively enumerated set with a graded structure (breadth first
search) with max_depth=3
sage: list(C)
[(0, 0),
 (1, 0), (0, 1),
 (2, 0), (1, 1), (0, 2),
 (3, 0), (2, 1), (1, 2), (0, 3)]

>>> from sage.all import *
>>> f = lambda a: [(a[Integer(0)]+Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]+Integer(1))]
>>> C = RecursivelyEnumeratedSet([(Integer(0),Integer(0))], f, structure='graded', max_depth=Integer(3))
>>> C
A recursively enumerated set with a graded structure (breadth first
search) with max_depth=3
>>> list(C)
[(0, 0),
 (1, 0), (0, 1),
 (2, 0), (1, 1), (0, 2),
 (3, 0), (2, 1), (1, 2), (0, 3)]
breadth_first_search_iterator(max_depth=None)[source]

Iterate on the elements of self (breadth first).

This iterator makes use of the graded structure by remembering only the elements of the current depth.

The elements are guaranteed to be enumerated in the order in which they are first visited (left-to-right traversal).

INPUT:

  • max_depth – (default: self._max_depth) specifies the maximal depth to which elements are computed

EXAMPLES:

sage: f = lambda a: [(a[0]+1,a[1]), (a[0],a[1]+1)]
sage: C = RecursivelyEnumeratedSet([(0,0)], f, structure='graded')
sage: list(C.breadth_first_search_iterator(max_depth=3))
[(0, 0),
 (1, 0), (0, 1),
 (2, 0), (1, 1), (0, 2),
 (3, 0), (2, 1), (1, 2), (0, 3)]

>>> from sage.all import *
>>> f = lambda a: [(a[Integer(0)]+Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]+Integer(1))]
>>> C = RecursivelyEnumeratedSet([(Integer(0),Integer(0))], f, structure='graded')
>>> list(C.breadth_first_search_iterator(max_depth=Integer(3)))
[(0, 0),
 (1, 0), (0, 1),
 (2, 0), (1, 1), (0, 2),
 (3, 0), (2, 1), (1, 2), (0, 3)]
graded_component(depth)[source]

Return the graded component of given depth.

This method caches each lower graded component. See graded_component_iterator() to generate each graded component without caching the previous ones.

A graded component is a set of elements of the same depth where the depth of an element is its minimal distance to a root.

INPUT:

  • depth – integer

OUTPUT: set

EXAMPLES:

sage: # needs sage.symbolic
sage: def f(a):
....:     return [a + 1, a + I]
sage: C = RecursivelyEnumeratedSet([0], f, structure='graded')
sage: for i in range(5): sorted(C.graded_component(i))
[0]
[I, 1]
[2*I, I + 1, 2]
[3*I, 2*I + 1, I + 2, 3]
[4*I, 3*I + 1, 2*I + 2, I + 3, 4]

>>> from sage.all import *
>>> # needs sage.symbolic
>>> def f(a):
...     return [a + Integer(1), a + I]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f, structure='graded')
>>> for i in range(Integer(5)): sorted(C.graded_component(i))
[0]
[I, 1]
[2*I, I + 1, 2]
[3*I, 2*I + 1, I + 2, 3]
[4*I, 3*I + 1, 2*I + 2, I + 3, 4]
graded_component_iterator()[source]

Iterate over the graded components of self.

A graded component is a set of elements of the same depth.

The algorithm remembers only the current graded component generated since the structure is graded.

OUTPUT: an iterator of sets

EXAMPLES:

sage: f = lambda a: [(a[0]+1,a[1]), (a[0],a[1]+1)]
sage: C = RecursivelyEnumeratedSet([(0,0)], f, structure='graded', max_depth=3)
sage: it = C.graded_component_iterator()
sage: for _ in range(4): sorted(next(it))
[(0, 0)]
[(0, 1), (1, 0)]
[(0, 2), (1, 1), (2, 0)]
[(0, 3), (1, 2), (2, 1), (3, 0)]

>>> from sage.all import *
>>> f = lambda a: [(a[Integer(0)]+Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]+Integer(1))]
>>> C = RecursivelyEnumeratedSet([(Integer(0),Integer(0))], f, structure='graded', max_depth=Integer(3))
>>> it = C.graded_component_iterator()
>>> for _ in range(Integer(4)): sorted(next(it))
[(0, 0)]
[(0, 1), (1, 0)]
[(0, 2), (1, 1), (2, 0)]
[(0, 3), (1, 2), (2, 1), (3, 0)]
class sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_symmetric[source]

Bases: RecursivelyEnumeratedSet_generic

Generic tool for constructing ideals of a symmetric relation.

INPUT:

  • seeds – list (or iterable) of hashable objects

  • successors – function (or callable) returning a list (or iterable)

  • enumeration – 'depth', 'breadth' or None (default: None)

  • max_depth – integer (default: float("inf"))

EXAMPLES:

sage: f = lambda a: [a-1,a+1]
sage: C = RecursivelyEnumeratedSet([0], f, structure='symmetric')
sage: C
A recursively enumerated set with a symmetric structure (breadth first search)
sage: it = iter(C)
sage: [next(it) for _ in range(7)]
[0, -1, 1, -2, 2, -3, 3]

>>> from sage.all import *
>>> f = lambda a: [a-Integer(1),a+Integer(1)]
>>> C = RecursivelyEnumeratedSet([Integer(0)], f, structure='symmetric')
>>> C
A recursively enumerated set with a symmetric structure (breadth first search)
>>> it = iter(C)
>>> [next(it) for _ in range(Integer(7))]
[0, -1, 1, -2, 2, -3, 3]
breadth_first_search_iterator(max_depth=None)[source]

Iterate on the elements of self (breadth first).

This iterator makes use of the graded structure by remembering only the last two graded components since the structure is symmetric.

The elements are guaranteed to be enumerated in the order in which they are first visited (left-to-right traversal).

INPUT:

  • max_depth – (default: self._max_depth) specifies the maximal depth to which elements are computed

EXAMPLES:

sage: f = lambda a: [(a[0]-1,a[1]), (a[0],a[1]-1), (a[0]+1,a[1]), (a[0],a[1]+1)]
sage: C = RecursivelyEnumeratedSet([(0,0)], f, structure='symmetric')
sage: s = list(C.breadth_first_search_iterator(max_depth=2)); s
[(0, 0),
 (-1, 0), (0, -1), (1, 0), (0, 1),
 (-2, 0), (-1, -1), (-1, 1), (0, -2), (1, -1), (2, 0), (1, 1), (0, 2)]

>>> from sage.all import *
>>> f = lambda a: [(a[Integer(0)]-Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]-Integer(1)), (a[Integer(0)]+Integer(1),a[Integer(1)]), (a[Integer(0)],a[Integer(1)]+Integer(1))]
>>> C = RecursivelyEnumeratedSet([(Integer(0),Integer(0))], f, structure='symmetric')
>>> s = list(C.breadth_first_search_iterator(max_depth=Integer(2))); s
[(0, 0),
 (-1, 0), (0, -1), (1, 0), (0, 1),
 (-2, 0), (-1, -1), (-1, 1), (0, -2), (1, -1), (2, 0), (1, 1), (0, 2)]

This iterator is used by default for symmetric structure:

sage: it = iter(C)
sage: s == [next(it) for _ in range(13)]
True

>>> from sage.all import *
>>> it = iter(C)
>>> s == [next(it) for _ in range(Integer(13))]
True
graded_component(depth)[source]

Return the graded component of given depth.

This method caches each lower graded component. See graded_component_iterator() to generate each graded component without caching the previous ones.

A graded component is a set of elements of the same depth where the depth of an element is its minimal distance to a root.

INPUT:

  • depth – integer

OUTPUT: set

EXAMPLES:

sage: f = lambda a: [a-1,a+1]
sage: C = RecursivelyEnumeratedSet([10, 15], f, structure='symmetric')
sage: for i in range(5): sorted(C.graded_component(i))
[10, 15]
[9, 11, 14, 16]
[8, 12, 13, 17]
[7, 18]
[6, 19]

>>> from sage.all import *
>>> f = lambda a: [a-Integer(1),a+Integer(1)]
>>> C = RecursivelyEnumeratedSet([Integer(10), Integer(15)], f, structure='symmetric')
>>> for i in range(Integer(5)): sorted(C.graded_component(i))
[10, 15]
[9, 11, 14, 16]
[8, 12, 13, 17]
[7, 18]
[6, 19]
graded_component_iterator()[source]

Iterate over the graded components of self.

A graded component is a set of elements of the same depth.

The enumeration remembers only the last two graded components generated since the structure is symmetric.

OUTPUT: an iterator of sets

EXAMPLES:

sage: f = lambda a: [a-1, a+1]
sage: S = RecursivelyEnumeratedSet([10], f, structure='symmetric')
sage: it = S.graded_component_iterator()
sage: [sorted(next(it)) for _ in range(5)]
[[10], [9, 11], [8, 12], [7, 13], [6, 14]]

>>> from sage.all import *
>>> f = lambda a: [a-Integer(1), a+Integer(1)]
>>> S = RecursivelyEnumeratedSet([Integer(10)], f, structure='symmetric')
>>> it = S.graded_component_iterator()
>>> [sorted(next(it)) for _ in range(Integer(5))]
[[10], [9, 11], [8, 12], [7, 13], [6, 14]]

Starting with two generators:

sage: f = lambda a: [a-1, a+1]
sage: S = RecursivelyEnumeratedSet([5, 10], f, structure='symmetric')
sage: it = S.graded_component_iterator()
sage: [sorted(next(it)) for _ in range(5)]
[[5, 10], [4, 6, 9, 11], [3, 7, 8, 12], [2, 13], [1, 14]]

>>> from sage.all import *
>>> f = lambda a: [a-Integer(1), a+Integer(1)]
>>> S = RecursivelyEnumeratedSet([Integer(5), Integer(10)], f, structure='symmetric')
>>> it = S.graded_component_iterator()
>>> [sorted(next(it)) for _ in range(Integer(5))]
[[5, 10], [4, 6, 9, 11], [3, 7, 8, 12], [2, 13], [1, 14]]

Gaussian integers:

sage: # needs sage.symbolic
sage: def f(a):
....:     return [a + 1, a + I]
sage: S = RecursivelyEnumeratedSet([0], f, structure='symmetric')
sage: it = S.graded_component_iterator()
sage: [sorted(next(it)) for _ in range(7)]
[[0],
 [I, 1],
 [2*I, I + 1, 2],
 [3*I, 2*I + 1, I + 2, 3],
 [4*I, 3*I + 1, 2*I + 2, I + 3, 4],
 [5*I, 4*I + 1, 3*I + 2, 2*I + 3, I + 4, 5],
 [6*I, 5*I + 1, 4*I + 2, 3*I + 3, 2*I + 4, I + 5, 6]]

>>> from sage.all import *
>>> # needs sage.symbolic
>>> def f(a):
...     return [a + Integer(1), a + I]
>>> S = RecursivelyEnumeratedSet([Integer(0)], f, structure='symmetric')
>>> it = S.graded_component_iterator()
>>> [sorted(next(it)) for _ in range(Integer(7))]
[[0],
 [I, 1],
 [2*I, I + 1, 2],
 [3*I, 2*I + 1, I + 2, 3],
 [4*I, 3*I + 1, 2*I + 2, I + 3, 4],
 [5*I, 4*I + 1, 3*I + 2, 2*I + 3, I + 4, 5],
 [6*I, 5*I + 1, 4*I + 2, 3*I + 3, 2*I + 4, I + 5, 6]]
sage.sets.recursively_enumerated_set.search_forest_iterator(roots, children, algorithm='depth')[source]

Return an iterator on the nodes of the forest having the given roots, and where children(x) returns the children of the node x of the forest. Note that every node of the tree is returned, not simply the leaves.

INPUT:

  • roots – list (or iterable)

  • children – a function returning a list (or iterable)

  • algorithm – 'depth' or 'breadth' (default: 'depth')

EXAMPLES:

We construct the prefix tree of binary sequences of length at most three, and enumerate its nodes:

sage: from sage.sets.recursively_enumerated_set import search_forest_iterator
sage: list(search_forest_iterator([[]], lambda l: [l + [0], l + [1]]
....:                                   if len(l) < 3 else []))
[[], [0], [0, 0], [0, 0, 0], [0, 0, 1], [0, 1], [0, 1, 0],
 [0, 1, 1], [1], [1, 0], [1, 0, 0], [1, 0, 1], [1, 1], [1, 1, 0], [1, 1, 1]]

>>> from sage.all import *
>>> from sage.sets.recursively_enumerated_set import search_forest_iterator
>>> list(search_forest_iterator([[]], lambda l: [l + [Integer(0)], l + [Integer(1)]]
...                                   if len(l) < Integer(3) else []))
[[], [0], [0, 0], [0, 0, 0], [0, 0, 1], [0, 1], [0, 1, 0],
 [0, 1, 1], [1], [1, 0], [1, 0, 0], [1, 0, 1], [1, 1], [1, 1, 0], [1, 1, 1]]

By default, the nodes are iterated through by depth first search. We can instead use a breadth first search (increasing depth):

sage: list(search_forest_iterator([[]], lambda l: [l + [0], l + [1]]
....:                                   if len(l) < 3 else [],
....:                             algorithm='breadth'))
[[],
 [0], [1],
 [0, 0], [0, 1], [1, 0], [1, 1],
 [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1],
 [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

>>> from sage.all import *
>>> list(search_forest_iterator([[]], lambda l: [l + [Integer(0)], l + [Integer(1)]]
...                                   if len(l) < Integer(3) else [],
...                             algorithm='breadth'))
[[],
 [0], [1],
 [0, 0], [0, 1], [1, 0], [1, 1],
 [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1],
 [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

This allows for iterating through trees of infinite depth:

sage: it = search_forest_iterator([[]], lambda l: [l + [0], l + [1]],
....:                             algorithm='breadth')
sage: [ next(it) for i in range(16) ]
[[],
 [0], [1], [0, 0], [0, 1], [1, 0], [1, 1],
 [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1],
 [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1],
 [0, 0, 0, 0]]

>>> from sage.all import *
>>> it = search_forest_iterator([[]], lambda l: [l + [Integer(0)], l + [Integer(1)]],
...                             algorithm='breadth')
>>> [ next(it) for i in range(Integer(16)) ]
[[],
 [0], [1], [0, 0], [0, 1], [1, 0], [1, 1],
 [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1],
 [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1],
 [0, 0, 0, 0]]

Here is an iterator through the prefix tree of sequences of letters in \(0,1,2\) without repetitions, sorted by length; the leaves are therefore permutations:

sage: list(search_forest_iterator([[]], lambda l: [l + [i] for i in range(3) if i not in l],
....:                             algorithm='breadth'))
[[],
 [0], [1], [2],
 [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1],
 [0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

>>> from sage.all import *
>>> list(search_forest_iterator([[]], lambda l: [l + [i] for i in range(Integer(3)) if i not in l],
...                             algorithm='breadth'))
[[],
 [0], [1], [2],
 [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1],
 [0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]