 |
 |
 |
Sage Reference Manual |  |
 |
 |
|
|
|
Sage Reference Manual | |
|
|
Module: sage.combinat.matrices.dlxcpp
Dancing links C++ wrapper
Module-level Functions
| M) |
Solves the exact cover problem on the matrix M (treated as a dense binary matrix).
No exact covers:
sage: M = Matrix([[1,1,0],[1,0,1],[0,1,1]]) sage: print [cover for cover in AllExactCovers(M)] []
Two exact covers:
sage: M = Matrix([[1,1,0],[1,0,1],[0,0,1],[0,1,0]]) sage: print [cover for cover in AllExactCovers(M)] [[(1, 1, 0), (0, 0, 1)], [(1, 0, 1), (0, 1, 0)]]
| rows) |
Solves the Exact Cover problem by using the Dancing Links algorithm described by Knuth.
Consider a matrix M with entries of 0 and 1, and compute a subset of the rows of this matrix which sum to the vector of all 1's.
The dancing links algorithm works particularly well for sparse matrices, so the input is a list of lists of the form: [ [i_11,i_12,...,i_1r] ... [i_m1,i_m2,...,i_ms] ] where M[j][i_jk] = 1.
The first example below corresponds to the matrix
1110 1010 0100 0001
which is exactly covered by
1110 0001
and
1010 0100 0001
If soln is a solution given by DLXCPP(rows) then
[ rows[soln[0]], rows[soln[1]], ... rows[soln[len(soln)-1]] ]
is an exact cover.
Solutions are given as a list
sage: rows = [[0,1,2]] sage: rows+= [[0,2]] sage: rows+= [[1]] sage: rows+= [[3]] sage: print [ x for x in DLXCPP(rows) ] [[3, 0], [3, 1, 2]]
| M) |
Solves the exact cover problem on the matrix M (treated as a dense binary matrix).
sage: M = Matrix([[1,1,0],[1,0,1],[0,1,1]]) #no exact covers sage: print OneExactCover(M) None sage: M = Matrix([[1,1,0],[1,0,1],[0,0,1],[0,1,0]]) #two exact covers sage: print OneExactCover(M) [(1, 1, 0), (0, 0, 1)]
|
|
|
Sage Reference Manual | |
|
|