# 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 a children function, with branch pruning, etc.

• SearchForest: Depth and breadth first search through a tree described by a children function.
• TransitiveIdeal: Depth first search through a graph described by a neighbours relation.
• TransitiveIdealGraded: Breadth first search through a graph described by a neighbours relation.

Deprecation details:

• SearchForest(seeds, succ) keeps the same behavior as before trac ticket #6637 and is now the same as RecursivelyEnumeratedSet(seeds, succ, structure='forest', enumeration='depth').
• TransitiveIdeal(succ, seeds) keeps the same behavior as before trac ticket #6637 and is now the same as RecursivelyEnumeratedSet(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 as RecursivelyEnumeratedSet(seeds, succ, structure=None, enumeration='breadth', max_depth=max_depth).

TODO:

• For now the code of SearchForest is still in sage/combinat/backtrack.py. It should be moved in sage/sets/recursively_enumerated_set.pyx into a class named RecursivelyEnumeratedSet_forest in a later ticket.
• TransitiveIdeal and TransitiveIealGraded are used in the code of sage/combinat, sage/categories and sage/groups at least. These should be updated to use RecursivelyEnumeratedSet in a later ticket for speed improvements.
• Once the deprecation has been there for enough time: delete TransitiveIdeal and TransitiveIealGraded.
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.

class sage.combinat.backtrack.PositiveIntegerSemigroup

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 integer x

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)

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.

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, 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: S = SearchForest( [[]],
....:     lambda l: [l+[0], l+[1]] if len(l) < 3 else [],
....:     category=FiniteEnumeratedSets())
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
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: tb = SearchForest( [[]],
....:       lambda l: [l + [i] for i in range(3) if i not in l],
....:       category=FiniteEnumeratedSets())
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
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: I = SearchForest([(0,0)],
....:                  lambda l: [(l[0]+1, l[1]), (l[0], 1)]
....:                            if l[1] == 0 else [(l[0], l[1]+1)])
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet


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

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


sage: breadth_search = I.breadth_first_search_iterator()
sage: [breadth_search.next() 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 and children functions as arguments to SearchForest.__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,
....:             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: [p.next() 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 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.combinat.backtrack import SearchForest
sage: class A(UniqueRepresentation, SearchForest):
....:     def __init__(self):
....:                               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: [p.next() 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())
An enumerated set with a forest structure


Return a breadth first search iterator over the elements of self

EXAMPLES:

sage: f = SearchForest([[]],
....:                  lambda l: [l+[0], l+[1]] if len(l) < 3 else [])
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
[[], [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)
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
sage: [p.next(), p.next(), p.next(), p.next(), p.next(), p.next(), p.next()]
[(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: I = SearchForest([(0,0)], lambda l: [(l[0]+1, l[1]), (l[0], 1)] if l[1] == 0 else [(l[0], l[1]+1)])
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
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: f = SearchForest([[]],
....:                  lambda l: [l+[0], l+[1]] if len(l) < 3 else [])
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
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: 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)
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
sage: p = S.elements_of_depth_iterator(8)
sage: p.next()
(5, 3)
sage: S = SearchForest(NN, lambda x : [],
....:                      lambda x: x^2 if x.is_prime() else None)
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
sage: p = S.elements_of_depth_iterator(0)
sage: [p.next(), p.next(), p.next(), p.next(), p.next()]
[4, 9, 25, 49, 121]

roots()

Return an iterable over the roots of self.

EXAMPLES:

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)])
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
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)

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 of generators.

Consider relation as modeling a directed graph (possibly with loops, cycles, or circuits). Then $$S$$ is the ideal generated by generators 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$$.

EXAMPLES:

sage: [i for i in TransitiveIdeal(lambda i: [i+1] if i<10 else [], [0])]
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
[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: [ f.next() 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, 2, 1], [3, 1, 2]]


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], [2, 1, 4, 3], [2, 4, 1, 3], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1], [3, 1, 2, 4], [2, 4, 3, 1], [3, 2, 1, 4], [2, 3, 1, 4], [2, 3, 4, 1], [3, 2, 4, 1], [3, 1, 4, 2], [3, 4, 2, 1], [3, 4, 1, 2], [4, 3, 1, 2]]


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


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 of generators.

Consider relation as modeling a directed graph (possibly with loops, cycles, or circuits). Then $$S$$ is the ideal generated by generators 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$$.

EXAMPLES:

sage: [i for i in TransitiveIdealGraded(lambda i: [i+1] if i<10 else [], [0])]
doctest:...: DeprecationWarning: This class soon will not be
available in that way anymore. Use RecursivelyEnumeratedSet
[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([ f.next() for i in range(3) ])
[-10, 0, 10]


The elements at distance 1 from the generators:

sage: sorted([ f.next() for i in range(6) ])
[-11, -9, -1, 1, 9, 11]


The elements at distance 2 from the generators:

sage: sorted([ f.next() 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, 1, 4, 3], [3, 2, 1, 4], [2, 3, 1, 4], [3, 1, 4, 2], [2, 3, 4, 1], [3, 4, 1, 2], [3, 2, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [4, 3, 1, 2], [4, 2, 1, 3], [3, 4, 2, 1], [4, 2, 3, 1], [4, 3, 2, 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 node x 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 [],
[[],
[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: [ it.next() 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 interator 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],
[[],
[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]]


Developer Tools

Output functions