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
. 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 or elements of given depth.
See Wikipedia article Recursively_enumerable_set.
See documentation of RecursivelyEnumeratedSet()
below for the
description of the inputs.
AUTHORS:
 Sébastien Labbé, April 2014, at Sage Days 57, Cernaylaville
EXAMPLES:
Forest structure¶
The set of words over the alphabet \(\{a,b\}\) can be generated from the empty word by appending 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
Depth first search iterator:
sage: it = C.depth_first_search_iterator()
sage: [next(it) for _ in range(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']
Symmetric structure¶
The origin (0, 0)
as seed and the upper, lower, left and right lattice
point as successor function. This function is symmetric:
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)
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)]
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)]
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)]
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)
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]]
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]]
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]]
Graded components (set of elements of the same depth):
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]]
No hypothesis on the structure¶
By “no hypothesis” is meant neither a forest nor symmetric nor graded, it may have other structure like not containing an oriented cycle but this does not help for enumeration.
In this example, the seed is 0 and the successor function is either +2
or +3
. This is the set of non negative 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)
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]
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]

sage.sets.recursively_enumerated_set.
RecursivelyEnumeratedSet
(seeds, successors, structure=None, enumeration=None, max_depth=None, post_process=None, facade=None, category=None)¶ 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 set that are described by some
seeds
and a successor functionsuccessors
.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\). Letseeds
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 thesuccessors
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 objectssuccessors
– function (or callable) returning a list (or iterable) of hashable objectsstructure
– string (optional, default:None
), structure of the set, possible values are:None
– nothing is known about the structure of the set.'forest'
– if thesuccessors
function generates a forest, that is, each element can be reached uniquely from a seed.'graded'
– if thesuccessors
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 ifx in successors(y)
enumeration
–'depth'
,'breadth'
,'naive'
orNone
(optional, default:None
). The default enumeration for the__iter__
function.max_depth
– integer (optional, default:float("inf")
), limit the search to a certain depth, currently works only for breadth first searchpost_process
– (optional, default:None
), for forest onlyfacade
– (optional, default:None
)category
– (optional, 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]
A recursive set with a forest structure:
sage: f = lambda a: [2*a,2*a+1] sage: C = RecursivelyEnumeratedSet([1], f, structure='forest') sage: 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]
A recursive set given by a symmetric relation:
sage: f = lambda a: [a1,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]
A recursive set given by a graded relation:
sage: f = lambda a: [a+1, a+I] sage: C = RecursivelyEnumeratedSet([0], f, structure='graded') sage: 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]
Warning
If you do not set the good structure, you might obtain bad results, like elements generated twice:
sage: f = lambda a: [a1,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]

class
sage.sets.recursively_enumerated_set.
RecursivelyEnumeratedSet_generic
¶ Bases:
sage.structure.parent.Parent
A generic recursively enumerated set.
For more information, see
RecursivelyEnumeratedSet()
.EXAMPLES:
sage: f = lambda a:[a+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
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)

breadth_first_search_iterator
(max_depth=None)¶ 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 (lefttoright 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]

depth_first_search_iterator
()¶ Iterate on the elements of
self
(depth first).This code remembers every elements generated.
The elements are traversed righttoleft, so the last element returned by the successor function is visited first.
See Wikipedia article Depthfirst_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]

elements_of_depth_iterator
(depth)¶ Iterate over the elements of
self
of given depth.An element of depth \(n\) can be obtained applying \(n\) times the successor function to a seed.
INPUT:
depth
– integer
OUTPUT:
An iterator.
EXAMPLES:
sage: f = lambda a: [a1, 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]

graded_component
(depth)¶ 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:
A 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

graded_component_iterator
()¶ 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

naive_search_iterator
()¶ Iterate on the elements of
self
(in no particular order).This code remembers every elements generated.

seeds
()¶ Return an iterable over the seeds of
self
.EXAMPLES:
sage: R = RecursivelyEnumeratedSet([1], lambda x: [x+1, x1]) sage: R.seeds() [1]

successors
¶

to_digraph
(max_depth=None, loops=True, multiedges=True)¶ 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 computedloops
– (default:True
) option for the digraphmultiedges
– (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() Looped multidigraph on 10 vertices
Digraph of an 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) Looped multidigraph 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() Looped multidigraph on 25 vertices
Digraph of an 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) Looped multidigraph on 21 vertices


class
sage.sets.recursively_enumerated_set.
RecursivelyEnumeratedSet_graded
¶ Bases:
sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic
Generic tool for constructing ideals of a graded relation.
INPUT:
seeds
– list (or iterable) of hashable objectssuccessors
– function (or callable) returning a list (or iterable)enumeration
–'depth'
,'breadth'
orNone
(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)]

breadth_first_search_iterator
(max_depth=None)¶ 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 (lefttoright 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)]

graded_component
(depth)¶ 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:
A set.
EXAMPLES:
sage: f = lambda a: [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]

graded_component_iterator
()¶ 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)]

class
sage.sets.recursively_enumerated_set.
RecursivelyEnumeratedSet_symmetric
¶ Bases:
sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic
Generic tool for constructing ideals of a symmetric relation.
INPUT:
seeds
– list (or iterable) of hashable objectssuccessors
– function (or callable) returning a list (or iterable)enumeration
–'depth'
,'breadth'
orNone
(default:None
)max_depth
– integer (default:float("inf")
)
EXAMPLES:
sage: f = lambda a: [a1,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]

breadth_first_search_iterator
(max_depth=None)¶ 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 (lefttoright 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)]
This iterator is used by default for symmetric structure:
sage: it = iter(C) sage: s == [next(it) for _ in range(13)] True

graded_component
(depth)¶ 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:
A set.
EXAMPLES:
sage: f = lambda a: [a1,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]

graded_component_iterator
()¶ 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: [a1, 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]]
Starting with two generators:
sage: f = lambda a: [a1, 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]]
Gaussian integers:
sage: f = lambda a: [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]]