Struct nekolib::algo::ExactCover

pub struct ExactCover { /* private fields */ }

Exact cover。

$n$ 行 $m$ 列の 0/1 行列 $A$ が与えられたとき、行 $\{0, 1, \dots, n-1\}$ の部分集合 $S$ であって、各列 $0\le j\lt m$ に対して $A_{i, j}=1$ なる $i\in S$ がちょうど 1 つ存在するものを探す。

$\gdef\I{\textcolor{red}{1}}$ $$ A = \begin{pmatrix} 0 & 0 & \I & 0 & \I & \I & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ \I & 0 & 0 & \I & 0 & 0 & 0 \\ 0 & \I & 0 & 0 & 0 & 0 & \I \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ \end{pmatrix} $$ のような行列 $A$ に対しては、$\{0, 3, 4\}$ が解となる。

Idea

Dancing links と呼ばれるデータ構造を用いる。

todo!()

Examples

use nekolib::algo::ExactCover;
let a = vec![                 
    vec![0, 0, 1, 0, 1, 1, 0],
    vec![1, 0, 0, 1, 0, 0, 1],
    vec![0, 1, 1, 0, 0, 1, 0],
    vec![1, 0, 0, 1, 0, 0, 0],
    vec![0, 1, 0, 0, 0, 0, 1],
    vec![0, 0, 0, 1, 1, 0, 1],
];
let ec = ExactCover::from_matrix(&a);
assert_eq!(ec.any(), Some(vec![3, 0, 4]));

References

• https://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz

Implementations

impl ExactCover

pub fn from_matrix(a: &Vec<Vec<usize>>) -> Self

与えられた行列に対して前計算を行う。

pub fn all(self) -> Vec<Vec<usize>>

解を全て探す。

pub fn any(self) -> Option<Vec<usize>>

解を探す。一つ見つかった時点で打ち切る。

Trait Implementations

impl Default for ExactCover

fn default() -> ExactCover

Returns the “default value” for a type.