Backtracking¶
This library contains generic tools for constructing large sets whose elements can be enumerated by exploring a search space with a (lazy) tree or graph structure.
GenericBacktracker
: Depth first search through a tree described by achildren
function, with branch pruning, etc.
Deprecated classes (use RecursivelyEnumeratedSet()
instead):
SearchForest
: Depth and breadth first search through a tree described by achildren
function.TransitiveIdeal
: Depth first search through a graph described by aneighbours
relation.TransitiveIdealGraded
: Breadth first search through a graph described by aneighbours
relation.
Deprecation details:
SearchForest(seeds, succ)
keeps the same behavior as before trac ticket #6637 and is now the same asRecursivelyEnumeratedSet(seeds, succ, structure='forest', enumeration='depth')
.TransitiveIdeal(succ, seeds)
keeps the same behavior as before trac ticket #6637 and is now the same asRecursivelyEnumeratedSet(seeds, succ, structure=None, enumeration='naive')
.TransitiveIdealGraded(succ, seeds, max_depth)
keeps the same behavior as before trac ticket #6637 and is now the same asRecursivelyEnumeratedSet(seeds, succ, structure=None, enumeration='breadth', max_depth=max_depth)
.
Todo
- For now the code of
SearchForest
is still insage/combinat/backtrack.py
. It should be moved insage/sets/recursively_enumerated_set.pyx
into a class namedRecursivelyEnumeratedSet_forest
in a later ticket. - Deprecate
TransitiveIdeal
andTransitiveIdealGraded
. - Once the deprecation has been there for enough time: delete
TransitiveIdeal
andTransitiveIdealGraded
.
-
class
sage.combinat.backtrack.
GenericBacktracker
(initial_data, initial_state)¶ Bases:
object
A generic backtrack tool for exploring a search space organized as a tree, with branch pruning, etc.
See also
SearchForest
andTransitiveIdeal
for handling simple special cases.
-
class
sage.combinat.backtrack.
PositiveIntegerSemigroup
¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.combinat.backtrack.SearchForest
The commutative additive semigroup of positive integers.
This class provides an example of algebraic structure which inherits from
SearchForest
. It builds the positive integers a la Peano, and endows it with its natural commutative additive semigroup structure.EXAMPLES:
sage: from sage.combinat.backtrack import PositiveIntegerSemigroup sage: PP = PositiveIntegerSemigroup() sage: PP.category() Join of Category of monoids and Category of commutative additive semigroups and Category of infinite enumerated sets and Category of facade sets sage: PP.cardinality() +Infinity sage: PP.one() 1 sage: PP.an_element() 1 sage: some_elements = list(PP.some_elements()); some_elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
TESTS:
sage: from sage.combinat.backtrack import PositiveIntegerSemigroup sage: PP = PositiveIntegerSemigroup()
We factor out the long test from the
TestSuite
:sage: TestSuite(PP).run(skip='_test_enumerated_set_contains') sage: PP._test_enumerated_set_contains() # long time
-
children
(x)¶ Return the single child
x+1
of the integerx
EXAMPLES:
sage: from sage.combinat.backtrack import PositiveIntegerSemigroup sage: PP = PositiveIntegerSemigroup() sage: list(PP.children(1)) [2] sage: list(PP.children(42)) [43]
-
one
()¶ Return the unit of
self
.EXAMPLES:
sage: from sage.combinat.backtrack import PositiveIntegerSemigroup sage: PP = PositiveIntegerSemigroup() sage: PP.one() 1
-
roots
()¶ Return the single root of
self
.EXAMPLES:
sage: from sage.combinat.backtrack import PositiveIntegerSemigroup sage: PP = PositiveIntegerSemigroup() sage: list(PP.roots()) [1]
-
-
class
sage.combinat.backtrack.
SearchForest
(roots=None, children=None, post_process=None, algorithm='depth', facade=None, category=None)¶ Bases:
sage.structure.parent.Parent
The enumerated set of the nodes of the forest having the given
roots
, and wherechildren(x)
returns the children of the nodex
of the forest.See also
GenericBacktracker
,TransitiveIdeal
, andTransitiveIdealGraded
.INPUT:
roots
– a 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, iff(x)
returnsNone
, thenx
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.combinat.backtrack import SearchForest sage: S = SearchForest( [[]], ....: 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]]
SearchForest
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
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.combinat.backtrack import SearchForest sage: tb = SearchForest( [[]], ....: 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]]
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.combinat.backtrack import SearchForest sage: I = SearchForest([(0,0)], ....: lambda l: [(l[0]+1, l[1]), (l[0], 1)] ....: if l[1] == 0 else [(l[0], l[1]+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)]
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)]
Deriving subclasses
The class of a parent \(A\) may derive from
SearchForest
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
SearchForest
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
andchildren
functions as arguments toSearchForest.__init__()
:sage: from sage.combinat.backtrack import SearchForest sage: class A(UniqueRepresentation, SearchForest): ....: def __init__(self): ....: SearchForest.__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]
An alternative approach is to implement
roots
andchildren
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, andA.children(x)
must return an iterable over the children of \(x\). Optionally, \(A\) can have a method or attribute such thatA.post_process(x)
returns the desired output for the nodex
of the tree:sage: from sage.combinat.backtrack import SearchForest sage: class A(UniqueRepresentation, SearchForest): ....: def __init__(self): ....: SearchForest.__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]
Warning
A
SearchForest
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 = SearchForest( [1], children, category=InfiniteEnumeratedSets()) sage: dumps(S) Traceback (most recent call last): ....: PicklingError: Can't pickle <type 'function'>: attribute lookup __builtin__.function failed
Let us now fake
children
being defined in a Python module:sage: import __main__ sage: __main__.children = children sage: S = SearchForest( [1], children, category=InfiniteEnumeratedSets()) sage: loads(dumps(S)) An enumerated set with a forest structure
-
breadth_first_search_iterator
()¶ Return a breadth first search iterator over the elements of
self
EXAMPLES:
sage: from sage.combinat.backtrack import SearchForest sage: f = SearchForest([[]], ....: 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 = SearchForest([(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)]
-
children
(x)¶ 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.combinat.backtrack import SearchForest sage: I = SearchForest([(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)]
-
depth_first_search_iterator
()¶ Return a depth first search iterator over the elements of
self
EXAMPLES:
sage: from sage.combinat.backtrack import SearchForest sage: f = SearchForest([[]], ....: 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]]
-
elements_of_depth_iterator
(depth=0)¶ Return an iterator over the elements of
self
of given depth. An element of depth \(n\) can be obtained applying \(n\) times the children function from a root.EXAMPLES:
sage: from sage.combinat.backtrack import SearchForest sage: S = SearchForest([(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 = SearchForest(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]
-
map_reduce
(map_function=None, reduce_function=None, reduce_init=None)¶ Apply a Map/Reduce algorithm on
self
INPUT:
map_function
– a function from the element ofself
to some set with a reduce operation (e.g.: a monoid). The default value is the constant function1
.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 is0
.
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: y = var('y') sage: def map_function(t): ....: li, sum, _ = t ....: return y ^ sum sage: reduce_function = lambda x,y: 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
Here is an example with the default values:
sage: F.map_reduce() 511
See also
-
roots
()¶ Return an iterable over the roots of
self
.EXAMPLES:
sage: from sage.combinat.backtrack import SearchForest sage: I = SearchForest([(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 = SearchForest([(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)]
-
class
sage.combinat.backtrack.
TransitiveIdeal
(succ, generators)¶ Bases:
sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic
Generic tool for constructing ideals of a relation.
INPUT:
relation
– a function (or callable) returning a list (or iterable)generators
– a list (or iterable)
Returns the set \(S\) of elements that can be obtained by repeated application of
relation
on the elements ofgenerators
.Consider
relation
as modeling a directed graph (possibly with loops, cycles, or circuits). Then \(S\) is the ideal generated bygenerators
under this relation.Enumerating the elements of \(S\) is achieved by depth first search through the graph. The time complexity is \(O(n+m)\) where \(n\) is the size of the ideal, and \(m\) the number of edges in the relation. The memory complexity is the depth, that is the maximal distance between a generator and an element of \(S\).
See also
SearchForest
andTransitiveIdealGraded
.EXAMPLES:
sage: from sage.combinat.backtrack import TransitiveIdeal sage: [i for i in TransitiveIdeal(lambda i: [i+1] if i<10 else [], [0])] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] sage: [i for i in TransitiveIdeal(lambda i: [mod(i+1,3)], [0])] [0, 1, 2] sage: [i for i in TransitiveIdeal(lambda i: [mod(i+2,3)], [0])] [0, 2, 1] sage: [i for i in TransitiveIdeal(lambda i: [mod(i+2,10)], [0])] [0, 2, 4, 6, 8] sage: [i for i in TransitiveIdeal(lambda i: [mod(i+3,10),mod(i+5,10)], [0])] [0, 3, 8, 1, 4, 5, 6, 7, 9, 2] sage: [i for i in TransitiveIdeal(lambda i: [mod(i+4,10),mod(i+6,10)], [0])] [0, 4, 8, 2, 6] sage: [i for i in TransitiveIdeal(lambda i: [mod(i+3,9)], [0,1])] [0, 1, 3, 4, 6, 7] sage: [p for p in TransitiveIdeal(lambda x:[x],[Permutation([3,1,2,4]), Permutation([2,1,3,4])])] [[2, 1, 3, 4], [3, 1, 2, 4]]
We now illustrate that the enumeration is done lazily, by depth first search:
sage: C = TransitiveIdeal(lambda x: [x-1, x+1], (-10, 0, 10)) sage: f = C.__iter__() sage: [ next(f) for i in range(6) ] [0, 1, 2, 3, 4, 5]
We compute all the permutations of 3:
sage: [p for p in TransitiveIdeal(attrcall("permutohedron_succ"), [Permutation([1,2,3])])] [[1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
We compute all the permutations which are larger than [3,1,2,4], [2,1,3,4] in the right permutohedron:
sage: [p for p in TransitiveIdeal(attrcall("permutohedron_succ"), [Permutation([3,1,2,4]), Permutation([2,1,3,4])])] [[2, 1, 3, 4], [3, 1, 2, 4], [2, 1, 4, 3], [3, 1, 4, 2], [2, 3, 1, 4], [3, 4, 1, 2], [3, 4, 2, 1], [2, 3, 4, 1], [2, 4, 1, 3], [3, 2, 1, 4], [4, 3, 1, 2], [4, 3, 2, 1], [3, 2, 4, 1], [4, 2, 1, 3], [2, 4, 3, 1], [4, 2, 3, 1]]
Using TransitiveIdeal people have been using the
__contains__
method provided from the__iter__
method. We need to make sure that this continues to work:sage: T = TransitiveIdeal(lambda a:[a+7,a+5], [0]) sage: 12 in T True
-
class
sage.combinat.backtrack.
TransitiveIdealGraded
(succ, generators, max_depth=inf)¶ Bases:
sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_generic
Generic tool for constructing ideals of a relation.
INPUT:
relation
– a function (or callable) returning a list (or iterable)generators
– a list (or iterable)max_depth
– (Default: infinity) Specifies the maximal depth to which elements are computed
Return the set \(S\) of elements that can be obtained by repeated application of
relation
on the elements ofgenerators
.Consider
relation
as modeling a directed graph (possibly with loops, cycles, or circuits). Then \(S\) is the ideal generated bygenerators
under this relation.Enumerating the elements of \(S\) is achieved by breadth first search through the graph; hence elements are enumerated by increasing distance from the generators. The time complexity is \(O(n+m)\) where \(n\) is the size of the ideal, and \(m\) the number of edges in the relation. The memory complexity is the depth, that is the maximal distance between a generator and an element of \(S\).
See also
SearchForest
andTransitiveIdeal
.EXAMPLES:
sage: from sage.combinat.backtrack import TransitiveIdealGraded sage: [i for i in TransitiveIdealGraded(lambda i: [i+1] if i<10 else [], [0])] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
We now illustrate that the enumeration is done lazily, by breadth first search:
sage: C = TransitiveIdealGraded(lambda x: [x-1, x+1], (-10, 0, 10)) sage: f = C.__iter__()
The elements at distance 0 from the generators:
sage: sorted([ next(f) for i in range(3) ]) [-10, 0, 10]
The elements at distance 1 from the generators:
sage: sorted([ next(f) for i in range(6) ]) [-11, -9, -1, 1, 9, 11]
The elements at distance 2 from the generators:
sage: sorted([ next(f) for i in range(6) ]) [-12, -8, -2, 2, 8, 12]
The enumeration order between elements at the same distance is not specified.
We compute all the permutations which are larger than [3,1,2,4] or [2,1,3,4] in the permutohedron:
sage: [p for p in TransitiveIdealGraded(attrcall("permutohedron_succ"), [Permutation([3,1,2,4]), Permutation([2,1,3,4])])] [[3, 1, 2, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 1, 4, 3], [3, 2, 1, 4], [3, 1, 4, 2], [3, 2, 4, 1], [2, 4, 1, 3], [3, 4, 1, 2], [2, 3, 4, 1], [4, 3, 1, 2], [3, 4, 2, 1], [4, 2, 1, 3], [2, 4, 3, 1], [4, 3, 2, 1], [4, 2, 3, 1]]
-
sage.combinat.backtrack.
search_forest_iterator
(roots, children, algorithm='depth')¶ Return an iterator on the nodes of the forest having the given roots, and where
children(x)
returns the children of the nodex
of the forest. Note that every node of the tree is returned, not simply the leaves.INPUT:
roots
– a 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.combinat.backtrack 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]]
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]]
This allows for iterating trough 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]]
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]]