nekolib/math/
bit_binom_.rs

1//! 組合せのビット表現。
2
3/// 組合せのビット表現。
4///
5/// $n$ bit で表せる整数のうち、$k$ 個の bit が `1` であるものを昇順に生成する。
6///
7/// # Idea
8///
9/// $k$ 個の bit が `1` である整数 `i` が与えられたとき、$k$ 個の bit が `1`
10/// である整数のうち `i` より大きく最小の整数 `j` を考える。
11///
12/// 例として `i = 011001110` とする。
13/// ```text
14/// 011001110  // i
15///     ^~~~
16/// ```
17/// `i` のうちで `1` が連続して現れる部分のうち、最も右のものを考える。
18/// これの左にある `0` の位は、`j` においては `1` である必要がある。
19/// ```text
20/// 011001110  // i
21/// 01101....  // j (upper)
22/// ```
23/// また、残った下位の領域においては、`i` における `1` の連続個数よりひとつ少ない
24/// `1` を右詰めで入れればよい。
25/// ```text
26/// 011001110  // i
27/// .....0011  // j (lower)
28/// ```
29///
30/// あとは、これらを計算する方法について述べる。
31/// ```text
32/// 011001110  // i
33/// 000000010  // x = i & i.wrapping_neg()
34/// 011010000  // y = i + x
35/// 000001110  // i & !y
36/// 000000011  // z = (i & !y) >> (x.trailing_zeros() + 1)
37/// 011010011  // j = y | z
38/// ```
39/// 上記では `_ >> (x.trailing_zeros() + 1)` としているが、`x` が 2
40/// べきなので `(_ / x) >> 1` と等しい。
41///
42/// # Examples
43/// ```
44/// use nekolib::math::bit_binom;
45///
46/// let mut it = bit_binom(4, 2);
47/// assert_eq!(it.next(), Some(0b_0011));
48/// assert_eq!(it.next(), Some(0b_0101));
49/// assert_eq!(it.next(), Some(0b_0110));
50/// assert_eq!(it.next(), Some(0b_1001));
51/// assert_eq!(it.next(), Some(0b_1010));
52/// assert_eq!(it.next(), Some(0b_1100));
53/// assert_eq!(it.next(), None);
54/// ```
55///
56/// # References
57/// - 蟻本 p.144
58pub fn bit_binom(n: usize, k: usize) -> impl Iterator<Item = usize> {
59    std::iter::successors(Some(!(!0_usize << k)), move |&i| {
60        if k == 0 {
61            return None;
62        }
63        let x = i & i.wrapping_neg();
64        let y = i + x;
65        let z = (i & !y) >> (x.trailing_zeros() + 1);
66        Some(y | z)
67    })
68    .take_while(move |&i| i < (1_usize << n))
69}
nekolib/math/bit_binom_.rs

nekolib/math/
bit_binom_.rs
