binom/
lib.rs

1pub trait Binom: Sized {
2    fn binom(self, k: Self) -> impl Iterator<Item = Self>;
3}
4
5macro_rules! impl_uint {
6    ( $($ty:ty)* ) => { $(
7        impl Binom for $ty {
8            fn binom(self, k: $ty) -> impl Iterator<Item = Self> {
9                let n = self;
10                std::iter::successors(Some(!(!(0 as $ty) << k)), move |&i| {
11                    if k == 0 {
12                        return None;
13                    }
14                    let x = i & i.wrapping_neg();
15                    let y = i + x;
16                    let z = (i & !y) >> (x.trailing_zeros() + 1);
17                    Some(y | z)
18                })
19                .take_while(move |&i| i < (1 << n))
20            }
21        }
22    )* }
23}
24
25impl_uint! { u8 u16 u32 u64 u128 usize }
26
27#[test]
28fn sanity_check() {
29    assert_eq!(5_u32.binom(3).collect::<Vec<_>>(), [
30        0b00111, 0b01011, 0b01101, 0b01110, 0b10011, 0b10101, 0b10110, 0b11001,
31        0b11010, 0b11100
32    ]);
33    assert_eq!(0_u32.binom(0).collect::<Vec<_>>(), [0]);
34    assert_eq!(1_u32.binom(0).collect::<Vec<_>>(), [0]);
35    assert_eq!(1_u32.binom(1).collect::<Vec<_>>(), [1]);
36}
binom/lib.rs

binom/
lib.rs
