Function nekolib::math::bit_binom_::bit_binom

pub fn bit_binom(n: usize, k: usize) -> impl Iterator<Item = usize>

組合せのビット表現。

$n$ bit で表せる整数のうち、$k$ 個の bit が 1 であるものを昇順に生成する。

Idea

$k$ 個の bit が 1 である整数 i が与えられたとき、$k$ 個の bit が 1 である整数のうち i より大きく最小の整数 j を考える。

例として i = 011001110 とする。

011001110  // i
    ^~~~

i のうちで 1 が連続して現れる部分のうち、最も右のものを考える。 これの左にある 0 の位は、j においては 1 である必要がある。

011001110  // i
01101....  // j (upper)

また、残った下位の領域においては、i における 1 の連続個数よりひとつ少ない 1 を右詰めで入れればよい。

011001110  // i
.....0011  // j (lower)

あとは、これらを計算する方法について述べる。

011001110  // i
000000010  // x = i & i.wrapping_neg()
011010000  // y = i + x
000001110  // i & !y
000000011  // z = (i & !y) >> (x.trailing_zeros() + 1)
011010011  // j = y | z

上記では _ >> (x.trailing_zeros() + 1) としているが、x が 2 べきなので (_ / x) >> 1 と等しい。

Examples

use nekolib::math::bit_binom;

let mut it = bit_binom(4, 2);
assert_eq!(it.next(), Some(0b_0011));
assert_eq!(it.next(), Some(0b_0101));
assert_eq!(it.next(), Some(0b_0110));
assert_eq!(it.next(), Some(0b_1001));
assert_eq!(it.next(), Some(0b_1010));
assert_eq!(it.next(), Some(0b_1100));
assert_eq!(it.next(), None);

References

• 蟻本 p.144