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 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: Breath 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)

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.

__init__(initial_data, initial_state)

EXAMPLES:

sage: from sage.combinat.backtrack import GenericBacktracker
sage: p = GenericBacktracker([], 1)
sage: loads(dumps(p))
<sage.combinat.backtrack.GenericBacktracker object at 0x...>
__iter__()

EXAMPLES:

sage: from sage.combinat.permutation import PatternAvoider
sage: p = PatternAvoider(4, [[1,3,2]])
sage: len(list(p))
14
__weakref__
list of weak references to the object (if defined)
class sage.combinat.backtrack.SearchForest(roots, children)

Returns the set of 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)

EXAMPLES:

A generator object for binary sequences of length 3, listed:

sage: list(SearchForest([[]], 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]]

A generator object for ordered sequences of length 2 from a 4-set, sampled:

sage: tb = SearchForest([[]], lambda l: [l + [i] for i in range(4) if i not in l] if len(l) < 2 else [])
sage: tb[0]
[]
sage: tb[16]
[3, 2]
__init__(roots, children)

TESTS:

sage: C = SearchForest((1,), lambda x: [x+1])
sage: C._roots
(1,)
sage: C._children
<function <lambda> at ...>
__iter__()

Returns an iterator on the elements of self.

EXAMPLES:

sage: def succ(l):
...        return [l+[0], l+[1]]
...
sage: C = SearchForest(([],), succ)
sage: f = C.__iter__()
sage: f.next()
[]
sage: f.next()
[0]
sage: f.next()
[0, 0]

sage: import __main__
sage: __main__.succ = succ # just because succ has been defined interactively
sage: loads(dumps(C))
An enumerated set
_repr_()

TESTS:

sage: SearchForest((1,), lambda x: [x+1])   # Todo: improve!
An enumerated set
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]]
__init__(succ, generators)

TESTS:

sage: C = TransitiveIdeal(factor, (1, 2, 3))
sage: C._succ
<function factor at ...>
sage: C._generators
(1, 2, 3)
sage: loads(dumps(C))   # should test for equality with C, but equality is not implemented
__iter__()

Returns an iterator on the elements of self.

TESTS:

sage: C = TransitiveIdeal(lambda x: [1,2], ())
sage: list(C) # indirect doctest
[]

sage: C = TransitiveIdeal(lambda x: [1,2], (1,))
sage: list(C) # indirect doctest
[1, 2]

sage: C = TransitiveIdeal(lambda x: [], (1,2))
sage: list(C) # indirect doctest
[1, 2]
class sage.combinat.backtrack.TransitiveIdealGraded(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 breath 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 illustrates that the enumeration is done lazily, by breath 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]]  
__init__(succ, generators)

TESTS:

sage: C = TransitiveIdealGraded(factor, (1, 2, 3))
sage: C._succ
<function factor at ...>
sage: C._generators
(1, 2, 3)
sage: loads(dumps(C))   # should test for equality with C, but equality is not implemented
__iter__()

Returns an iterator on the elements of self.

TESTS:

sage: C = TransitiveIdeal(lambda x: [1,2], ())
sage: list(C) # indirect doctest
[]

sage: C = TransitiveIdeal(lambda x: [1,2], (1,))
sage: list(C) # indirect doctest
[1, 2]

sage: C = TransitiveIdeal(lambda x: [], (1,2))
sage: list(C) # indirect doctest
[1, 2]
sage.combinat.backtrack.search_forest_iterator(roots, children)

Returns 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)

EXAMPLES:

Search tree where leaves are binary sequences of length 3:

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]]

Search tree where leaves are ordered sequences of length 2 from a 4-set:

sage: from sage.combinat.backtrack import search_forest_iterator
sage: list(search_forest_iterator([[]], lambda l: [l + [i] for i in range(4) if i not in l] if len(l) < 2 else []))
[[], [0], [0, 1], [0, 2], [0, 3], [1], [1, 0], [1, 2], [1, 3], [2], [2, 0], [2, 1], [2, 3], [3], [3, 0], [3, 1], [3, 2]]

Previous topic

Developer Tools

Next topic

Output functions

This Page