Navigation

  • index
  • modules |
  • next |
  • previous |
  • Combinatorics »
  • Comprehensive Module list »

Dancing Links internal pyx code¶

class sage.combinat.matrices.dancing_links.dancing_linksWrapper¶

Bases: object

A simple class that implements dancing links.

The main methods to list the solutions are search() and get_solution(). You can also use number_of_solutions() to count them.

This class simply wraps a C++ implementation of Carlo Hamalainen.

get_solution()¶

Return the current solution.

After a new solution is found using the method search() this method return the rows that make up the current solution.

number_of_solutions(ncpus=1, column=0)¶

Return the number of distinct solutions.

INPUT:

  • ncpus – integer (default: 1), maximal number of subprocesses to use at the same time. If \(ncpus>1\) the dancing links problem is split into independent subproblems to allow parallel computation.
  • column – integer (default: 0), the column used to split the problem (ignored if ncpus is 1)

OUTPUT:

integer

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2]]
sage: rows += [[0,2]]
sage: rows += [[1]]
sage: rows += [[3]]
sage: x = dlx_solver(rows)
sage: x.number_of_solutions()
2
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: x = dlx_solver(rows)
sage: x.number_of_solutions(ncpus=2, column=3)
3
rows()¶

Return the list of rows.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [1,2], [0]]
sage: x = dlx_solver(rows)
sage: x.rows()
[[0, 1, 2], [1, 2], [0]]
search()¶

Search for a new solution.

Return 1 if a new solution is found and 0 otherwise. To recover the solution, use the method get_solution().

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2]]
sage: rows+= [[0,2]]
sage: rows+= [[1]]
sage: rows+= [[3]]
sage: x = dlx_solver(rows)
sage: print(x.search())
1
sage: print(x.get_solution())
[3, 0]
solutions_iterator()¶

Return an iterator of the solutions.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: list(d.solutions_iterator())
[[0, 1], [2, 3], [4, 5]]
split(column)¶

Return a dict of rows solving independent cases.

For each i-th row containing a 1 in the column, the dict associates the list of rows where each other row containing a 1 in the same column is replaced by the empty list.

This is used for parallel computations.

INPUT:

  • column – integer, the column used to split the problem

OUTPUT:

dict where keys are row numbers and values are lists of rows

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]]
sage: d = dlx_solver(rows)
sage: d
Dancing links solver for 6 columns and 6 rows
sage: sorted(d.solutions_iterator())
[[0, 1], [2, 3], [4, 5]]

After the split each subproblem has the same number of columns and rows as the original one:

sage: D = d.split(0)
sage: D
{0: [[0, 1, 2], [3, 4, 5], [], [2, 3, 4, 5], [], [1, 2, 3, 4, 5]],
 2: [[], [3, 4, 5], [0, 1], [2, 3, 4, 5], [], [1, 2, 3, 4, 5]],
 4: [[], [3, 4, 5], [], [2, 3, 4, 5], [0], [1, 2, 3, 4, 5]]}

The (disjoint) union of the solutions of the subproblems is equal to the set of solutions shown above:

sage: for a in D.values(): list(dlx_solver(a).solutions_iterator())
[[0, 1]]
[[2, 3]]
[[4, 5]]
sage.combinat.matrices.dancing_links.dlx_solver(rows)¶

Internal-use wrapper for the dancing links C++ code.

EXAMPLES:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = [[0,1,2]]
sage: rows+= [[0,2]]
sage: rows+= [[1]]
sage: rows+= [[3]]
sage: x = dlx_solver(rows)
sage: print(x.search())
1
sage: print(x.get_solution())
[3, 0]
sage: print(x.search())
1
sage: print(x.get_solution())
[3, 1, 2]
sage: print(x.search())
0
sage.combinat.matrices.dancing_links.make_dlxwrapper(s)¶

Create a dlx wrapper from a Python string s.

This was historically used in unpickling and is kept for backwards compatibility. We expect s to be dumps(rows) where rows is the list of rows used to instantiate the object.

Previous topic

Combinatorics on matrix features that are imported by default in the interpreter namespace

Next topic

Dancing links C++ wrapper

This Page

  • Show Source

Quick search

Enter search terms or a module, class or function name.

Navigation

  • index
  • modules |
  • next |
  • previous |
  • Combinatorics »
  • Comprehensive Module list »
© Copyright 2005--2016, The Sage Development Team. Created using Sphinx 1.6.3.