Backtracking

This library contains a generic tool 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.

This module has mostly been superseded by RecursivelyEnumeratedSet.

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 RecursivelyEnumeratedSet_forest for handling simple special cases.

class sage.combinat.backtrack.PositiveIntegerSemigroup

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.sets.recursively_enumerated_set.RecursivelyEnumeratedSet_forest

The commutative additive semigroup of positive integers.

This class provides an example of algebraic structure which inherits from RecursivelyEnumeratedSet_forest. 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]
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]