haar_lib/algo/
enum_groups.rs

1//! グループ分けの方法の全列挙
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc390/tasks/abc390_d>
5
6use crate::algo::enum_bit::subset_asc::*;
7
8/// `n`個の区別できるものをグループ分けする方法をすべて列挙する。
9/// グループ分けの方法の個数はベル数となる。
10///
11/// `proc`はグループ分けの結果を受け取って処理する。
12/// 一つのグループは、`i`番目の要素が含まれていれば、`i`番目のビットが立っているような、`u32`で返される。
13pub fn enum_groups<F>(n: usize, mut proc: F)
14where
15    F: FnMut(&Vec<u32>),
16{
17    rec(n, 0, &mut proc, &mut vec![]);
18}
19
20fn rec<F>(n: usize, bit: u32, proc: &mut F, gs: &mut Vec<u32>)
21where
22    F: FnMut(&Vec<u32>),
23{
24    let mask = (1 << n) - 1;
25    if bit == mask {
26        proc(gs);
27    } else {
28        let left_unused = bit.trailing_ones();
29        let left = 1 << left_unused;
30        for rest in subset_asc((mask & !bit) ^ left) {
31            let g = rest | left;
32            gs.push(g);
33            rec(n, bit | g, proc, gs);
34            gs.pop();
35        }
36    }
37}
haar_lib/algo/enum_groups.rs

haar_lib/algo/
enum_groups.rs
