haar_lib/algo/enum_bit/
subset_asc.rs

1//! ビット列の部分集合を昇順に列挙する
2use std::iter::successors;
3
4/// ビット列としての`a`の部分集合を昇順に列挙するイテレータを返す。
5pub fn subset_asc(a: u32) -> impl Iterator<Item = u32> {
6    successors(Some(0), move |&t| {
7        (t != a).then_some(((t as i32 - a as i32) & (a as i32)) as u32)
8    })
9}
10
11#[cfg(test)]
12mod tests {
13    use super::*;
14    use test_case::test_case;
15
16    #[test_case(0b11111111)]
17    #[test_case(0b00000000)]
18    #[test_case(0b10101010)]
19    #[test_case(0b00000001)]
20    #[test_case(0b10000000)]
21    #[test_case(0b10000001)]
22    #[test_case(0b11011011)]
23    fn check(x: u32) {
24        let a = (0..=x).filter(|i| (!x & i) == 0).collect::<Vec<_>>();
25
26        let b = subset_asc(x).collect::<Vec<_>>();
27
28        assert_eq!(a, b);
29    }
30}