Struct nekolib::algo::exact_cover::ExactCover
source · pub struct ExactCover { /* private fields */ }
Expand description
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
Implementations§
Trait Implementations§
source§impl Default for ExactCover
impl Default for ExactCover
source§fn default() -> ExactCover
fn default() -> ExactCover
Returns the “default value” for a type. Read more
Auto Trait Implementations§
impl RefUnwindSafe for ExactCover
impl Send for ExactCover
impl Sync for ExactCover
impl Unpin for ExactCover
impl UnwindSafe for ExactCover
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more