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.

  • SearchForest: Depth and breadth first search through a tree described by a children function.
  • GenericBacktracker: Depth first search through a tree described by a children function, with branch pruning, etc.
  • TransitiveIdeal: Depth first search through a graph described by a neighbours relation.
  • TransitiveIdealGraded: Breadth first search through a graph described by a neighbours relation.

TODO:

  1. Find a good and consistent naming scheme! Do we want to emphasize the underlying graph/tree structure? The branch & bound aspect? The transitive closure of a relation point of view?
  2. Do we want TransitiveIdeal(relation, generators) or TransitiveIdeal(generators, relation)? The code needs to be standardized once the choice is made.
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 and TransitiveIdeal 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 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)

Bases: sage.structure.parent.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 GenericBacktracker, TransitiveIdeal, and TransitiveIdealGraded.

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)
  • algorithmdepth 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())
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],
....:       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: 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: [depth_search.next() 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: [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: 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: [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: 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: [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())
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: 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: [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)])
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 [])
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)
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)
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)])
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\).

See also SearchForest and TransitiveIdealGraded.

EXAMPLES:

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: [ 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]]
class sage.combinat.backtrack.TransitiveIdealGraded(succ, generators, max_depth=inf)

Bases: sage.combinat.backtrack.TransitiveIdeal

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\).

See also SearchForest and TransitiveIdeal.

EXAMPLES:

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([ 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)
  • algorithmdepth 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: [ 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],
....:                             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]]

Previous topic

Developer Tools

Next topic

Output functions

This Page