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()
andget_solution()
. You can also usenumber_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 ifncpus
is1
)
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 and0
otherwise. To recover the solution, use the methodget_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 a1
in thecolumn
, the dict associates the list of rows where each other row containing a1
in the samecolumn
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 rowsEXAMPLES:
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