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.

TESTS:

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

TESTS:

sage: dlx_solver([]).number_of_solutions()
0
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]

TESTS:

Test that trac ticket #11814 is fixed:

sage: dlx_solver([]).search()
0
sage: dlx_solver([[]]).search()
0

If search is called once too often, it keeps returning 0:

sage: x = dlx_solver([[0]])
sage: x.search()
1
sage: x.search()
0
sage: x.search()
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.

TESTS:

sage: from sage.combinat.matrices.dancing_links import make_dlxwrapper
sage: rows = [[0,1,2]]
sage: x = make_dlxwrapper(dumps(rows))
sage: print(x.__str__())
Dancing links solver for 3 columns and 1 rows

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.4.9.