nekolib/algo/
exact_cover.rs

1//! Exact cover。
2
3/// Exact cover。
4///
5/// $n$ 行 $m$ 列の 0/1 行列 $A$ が与えられたとき、行 $\\{0, 1, \\dots, n-1\\}$
6/// の部分集合 $S$ であって、各列 $0\\le j\\lt m$ に対して $A\_{i, j}=1$ なる
7/// $i\\in S$ がちょうど 1 つ存在するものを探す。
8///
9/// $\\gdef\\I{\\textcolor{red}{1}}$
10/// $$ A = \\begin{pmatrix}
11/// 0 & 0 & \\I & 0 & \\I & \\I & 0 \\\\
12/// 1 & 0 & 0 & 1 & 0 & 0 & 1 \\\\
13/// 0 & 1 & 1 & 0 & 0 & 1 & 0 \\\\
14/// \\I & 0 & 0 & \\I & 0 & 0 & 0 \\\\
15/// 0 & \\I & 0 & 0 & 0 & 0 & \\I \\\\
16/// 0 & 0 & 0 & 1 & 1 & 0 & 1 \\\\
17/// \\end{pmatrix} $$
18/// のような行列 $A$ に対しては、$\\{0, 3, 4\\}$ が解となる。
19///
20/// # Idea
21/// Dancing links と呼ばれるデータ構造を用いる。
22///
23/// `todo!()`
24///
25/// # Examples
26/// ```
27/// use nekolib::algo::ExactCover;
28/// let a = vec![                 
29///     vec![0, 0, 1, 0, 1, 1, 0],
30///     vec![1, 0, 0, 1, 0, 0, 1],
31///     vec![0, 1, 1, 0, 0, 1, 0],
32///     vec![1, 0, 0, 1, 0, 0, 0],
33///     vec![0, 1, 0, 0, 0, 0, 1],
34///     vec![0, 0, 0, 1, 1, 0, 1],
35/// ];
36/// let ec = ExactCover::from_matrix(&a);
37/// assert_eq!(ec.any(), Some(vec![3, 0, 4]));
38/// ```
39///
40/// # References
41/// - <https://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz>
42#[derive(Default)]
43pub struct ExactCover {
44    link: Vec<Node>,
45    size: Vec<usize>,
46    row: Vec<usize>,
47    col: Vec<usize>,
48}
49
50#[derive(Clone, Copy, Debug, Default)]
51struct Node {
52    left: usize,
53    right: usize,
54    up: usize,
55    down: usize,
56}
57
58impl ExactCover {
59    /// 与えられた行列に対して前計算を行う。
60    pub fn from_matrix(a: &Vec<Vec<usize>>) -> Self {
61        let h = a.len();
62        if h == 0 {
63            return Self::default();
64        }
65        let w = a[0].len();
66        let mut index = vec![vec![0; w]; h];
67        let mut size = vec![0; w];
68        let mut row = vec![0; w + 1];
69        let mut col = vec![0; w + 1];
70        let mut cur = w;
71        for i in 0..h {
72            for j in 0..w {
73                if a[i][j] == 0 {
74                    continue;
75                }
76                cur += 1;
77                index[i][j] = cur;
78                size[j] += 1;
79                row.push(i);
80                col.push(j);
81            }
82        }
83
84        let mut link = vec![Node::default(); cur + 1];
85        link[0].right = 1;
86        link[0].left = w;
87        link[w].right = 0;
88        link[w].left = w - 1;
89        for j in 1..w {
90            link[j].right = j + 1;
91            link[j].left = j - 1;
92        }
93        for i in 0..h {
94            let first = match (0..w).find(|&j| index[i][j] != 0) {
95                Some(s) => s,
96                None => continue,
97            };
98            let mut j = first;
99            loop {
100                match (j + 1..w).find(|&nj| index[i][nj] != 0) {
101                    Some(nj) => {
102                        link[index[i][j]].right = index[i][nj];
103                        link[index[i][nj]].left = index[i][j];
104                        j = nj;
105                    }
106                    None => {
107                        link[index[i][first]].left = index[i][j];
108                        link[index[i][j]].right = index[i][first];
109                        break;
110                    }
111                };
112            }
113        }
114
115        for j in 0..w {
116            let first = match (0..h).find(|&i| index[i][j] != 0) {
117                Some(s) => s,
118                None => continue,
119            };
120            let mut i = first;
121            link[j + 1].down = index[i][j];
122            link[index[i][j]].up = j + 1;
123            loop {
124                match (i + 1..h).find(|&ni| index[ni][j] != 0) {
125                    Some(ni) => {
126                        link[index[i][j]].down = index[ni][j];
127                        link[index[ni][j]].up = index[i][j];
128                        i = ni;
129                    }
130                    None => {
131                        link[j + 1].up = index[i][j];
132                        link[index[i][j]].down = j + 1;
133                        break;
134                    }
135                }
136            }
137        }
138
139        Self { link, size, row, col }
140    }
141
142    /// 解を全て探す。
143    pub fn all(mut self) -> Vec<Vec<usize>> {
144        if self.link.is_empty() || self.size.iter().any(|&x| x == 0) {
145            return vec![];
146        }
147
148        let mut res = vec![];
149        let mut cur = vec![];
150        self.dfs(&mut cur, &mut res, false);
151        res
152    }
153
154    /// 解を探す。一つ見つかった時点で打ち切る。
155    pub fn any(mut self) -> Option<Vec<usize>> {
156        if self.link.is_empty() || self.size.iter().any(|&x| x == 0) {
157            return None;
158        }
159
160        let mut res = vec![];
161        let mut cur = vec![];
162        self.dfs(&mut cur, &mut res, true);
163        res.pop()
164    }
165
166    fn dfs(
167        &mut self,
168        cur: &mut Vec<usize>,
169        res: &mut Vec<Vec<usize>>,
170        any: bool,
171    ) {
172        if self.link[0].right == 0 {
173            res.push(cur.clone());
174            return;
175        }
176
177        let c = self.choose();
178        self.cover(c);
179        let mut r = self.link[c].down;
180        while r != c {
181            cur.push(self.row[r]);
182            let mut j = self.link[r].right;
183            while j != r {
184                self.cover(self.col[j] + 1);
185                j = self.link[j].right;
186            }
187            self.dfs(cur, res, any);
188            if any && !res.is_empty() {
189                return;
190            }
191
192            cur.pop();
193            let mut j = self.link[r].left;
194            while j != r {
195                self.uncover(self.col[j] + 1);
196                j = self.link[j].left;
197            }
198            r = self.link[r].down;
199        }
200
201        self.uncover(c);
202    }
203
204    fn choose(&self) -> usize {
205        let mut j = self.link[0].right;
206        let mut c = j;
207        let mut s = self.size[j - 1];
208        while j != 0 {
209            if self.size[j - 1] < s {
210                c = j;
211                s = self.size[j - 1];
212            }
213            j = self.link[j].right;
214        }
215        c
216    }
217
218    fn cover(&mut self, c: usize) {
219        let left = self.link[c].left;
220        let right = self.link[c].right;
221        self.link[right].left = left;
222        self.link[left].right = right;
223        let mut i = self.link[c].down;
224        while i != c {
225            let mut j = self.link[i].right;
226            while j != i {
227                let up = self.link[j].up;
228                let down = self.link[j].down;
229                self.link[down].up = up;
230                self.link[up].down = down;
231                self.size[self.col[j]] -= 1;
232                j = self.link[j].right;
233            }
234            i = self.link[i].down;
235        }
236    }
237
238    fn uncover(&mut self, c: usize) {
239        let mut i = self.link[c].up;
240        while i != c {
241            let mut j = self.link[i].left;
242            while j != i {
243                self.size[self.col[j]] += 1;
244                let down = self.link[j].down;
245                let up = self.link[j].up;
246                self.link[down].up = j;
247                self.link[up].down = j;
248                j = self.link[j].left;
249            }
250            i = self.link[i].up;
251        }
252        let right = self.link[c].right;
253        let left = self.link[c].left;
254        self.link[right].left = c;
255        self.link[left].right = c;
256    }
257}
nekolib/algo/exact_cover.rs

nekolib/algo/
exact_cover.rs
