Recursively enumerated set
A set is called recursively enumerable if there is an algorithm that
enumerates the members of
. 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:
EXAMPLES:
The set of words over the alphabet can be generated from the
empty word by appending letter
or
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']
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(10)]
[(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (-1, 1), (-2, 0), (0, 2), (2, 0), (-1, -1)]
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)]
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],
[1, 3, 2, 4, 5],
[1, 2, 4, 3, 5],
[2, 1, 3, 4, 5],
[1, 2, 3, 5, 4]]
Elements of given depth iterator:
sage: list(R.elements_of_depth_iterator(9))
[[5, 4, 2, 3, 1], [4, 5, 3, 2, 1], [5, 3, 4, 2, 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]]
By “no hypothesis” is meant neither a forest, neither symmetric neither graded, it may have other structure like not containing 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, 8, 9, 7, 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]
Return a recursively enumerated set.
A set is called recursively enumerable if there is an algorithm that
enumerates the members of
. We consider here the recursively
enumerated set that are described by some seeds and a successor
function successors.
Let be a set and successors
be a successor function
associating to each element of
a subset of
. Let seeds be a
subset of
. Let
be the set of elements of
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
.
See Wikipedia article Recursively_enumerable_set.
INPUT:
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, 8, 10, 6, 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: [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, 16, 9, 11, 14, 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, I + 1, 2, 2*I, I + 2]
Warning
If you do not set the 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, 0, 2, -2, 1]
TESTS:
The succesors method is an attribute:
sage: R = RecursivelyEnumeratedSet([1], lambda x: [x+1, x-1])
sage: R.successors(4)
[5, 3]
sage: C = RecursivelyEnumeratedSet((1, 2, 3), factor)
sage: C.successors
<function factor at ...>
sage: C._seeds
(1, 2, 3)
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)
Iterate on the elements of self (breadth first).
This code remembers every elements generated.
INPUT:
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, 8, 10, 6, 9, 11, 13, 15]
Iterate on the elements of self (depth first).
This code remembers every elements generated.
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]
Iterate over the elements of self of given depth.
An element of depth can be obtained applying
times the
successor function to a seed.
INPUT:
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]
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.
INPUT:
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
When the structure is symmetric:
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]
When the structure is graded:
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]
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 herited classes.
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
Iterate on the elements of self (in no particular order).
This code remembers every elements generated.
TESTS:
We compute all the permutations of 3:
sage: seeds = [Permutation([1,2,3])]
sage: succ = attrcall("permutohedron_succ")
sage: R = RecursivelyEnumeratedSet(seeds, succ)
sage: list(R.naive_search_iterator())
[[1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
Return an iterable over the seeds of self.
EXAMPLES:
sage: R = RecursivelyEnumeratedSet([1], lambda x: [x+1, x-1])
sage: R.seeds()
[1]
Bases: sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic
Generic tool for constructing ideals of a graded relation.
INPUT:
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)
sage: sorted(C)
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0),
(1, 1), (1, 2), (2, 0), (2, 1), (3, 0)]
Iterate on the elements of self (breadth first).
This iterator make use of the graded structure by remembering only the elements of the current depth.
INPUT:
EXAMPLES:
sage: f = lambda a: [(a[0]+1,a[1]), (a[0],a[1]+1)]
sage: C = RecursivelyEnumeratedSet([(0,0)], f, structure='graded')
sage: it = C.breadth_first_search_iterator(max_depth=3)
sage: list(it)
[(0, 0), (0, 1), (1, 0), (2, 0), (1, 1),
(0, 2), (3, 0), (1, 2), (0, 3), (2, 1)]
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)]
Bases: sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic
Generic tool for constructing ideals of a symmetric relation.
INPUT:
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]
TESTS:
Do not use lambda functions for saving purposes:
sage: f = lambda a: [a-1,a+1]
sage: C = RecursivelyEnumeratedSet([0], f, structure='symmetric')
sage: loads(dumps(C))
Traceback (most recent call last):
...
PicklingError: Can't pickle <type 'function'>: attribute lookup __builtin__.function failed
This works in the command line but apparently not as a doctest:
sage: def f(a): return [a-1,a+1]
sage: C = RecursivelyEnumeratedSet([0], f, structure='symmetric')
sage: loads(dumps(C))
Traceback (most recent call last):
...
PicklingError: Can't pickle <type 'function'>: attribute lookup __builtin__.function failed
Iterate on the elements of self (breadth first).
INPUT:
Note
It should be slower than the other one since it must generates the whole graded component before yielding the first element of each graded component. It is used for test only.
EXAMPLES:
sage: f = lambda a: [(a[0]+1,a[1]), (a[0],a[1]+1)]
sage: C = RecursivelyEnumeratedSet([(0,0)], f, structure='graded')
sage: it = C._breadth_first_search_iterator_from_graded_component_iterator(max_depth=3)
sage: list(it)
[(0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2)]
This iterator is used by default for symmetric structure:
sage: f = lambda a: [a-1,a+1]
sage: S = RecursivelyEnumeratedSet([10], f, structure='symmetric')
sage: it = iter(S)
sage: [next(it) for _ in range(7)]
[10, 9, 11, 8, 12, 13, 7]
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]]
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]]
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]]