bit_permutations.rs

// Implements the cool-lex algorithm to generate (n,k)-combinations
// @article{Ruskey:2009fk,
//  Author = {Frank Ruskey and Aaron Williams},
//  Doi = {10.1016/j.disc.2007.11.048},
//  Journal = {Discrete Mathematics},
//  Month = {September},
//  Number = {17},
//  Pages = {5305-5320},
//  Title = {The coolest way to generate combinations},
//  Url = {http://www.sciencedirect.com/science/article/pii/S0012365X07009570},
//  Volume = {309},
//  Year = {2009}}
pub fn visit_combinations<F: Fn(u64)>(zeros: u32, ones: u32, visit: F) {
    assert!(64_u32.saturating_sub(zeros).saturating_sub(ones) > 0,
        "max 63 bits allowed for permutations");
    if ones == 0 {
        visit(0);
        return;
    }
    let limit_mask = 1 << (zeros + ones);
    let mut current = (1 << ones) - 1;
    while limit_mask & current == 0 {
        visit(current);
        let lowest_zero = current & (current + 1);
        let suffix_mask = lowest_zero ^ lowest_zero.wrapping_sub(1);
        let next_bit_mask = suffix_mask.wrapping_add(1);
        let suffix = suffix_mask & current;
        let next_bit_m1 = (next_bit_mask & current).saturating_sub(1);
        current = current + suffix - next_bit_m1;
    }
}

pub struct BitPermutations {
    limit_mask: u64,
    current: u64,
}

impl BitPermutations {
    pub fn new(zeros: u32, ones: u32) -> Self {
        assert!(ones != 0, "not supported iterating over one 0");
        assert!(64_u32.saturating_sub(zeros).saturating_sub(ones) > 0,
            "max 63 bits allowed for permutations");
        Self {
            limit_mask: 1 << (zeros + ones),
            current: (1 << ones) - 1,
        }
    }
}

impl Iterator for BitPermutations {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let &mut Self { limit_mask, current } = self;
        if limit_mask & current != 0 {
            return None;
        }

        let lowest_zero = current & (current + 1);
        let suffix_mask = lowest_zero ^ lowest_zero.wrapping_sub(1);
        let suffix = suffix_mask & current;
        let next_bit_mask = suffix_mask.wrapping_add(1);
        let next_bit_m1 = (next_bit_mask & current).saturating_sub(1);
        self.current = current + suffix - next_bit_m1;
        Some(current)
    }
}

#[test]
fn main() {
    visit_combinations(4, 4, |w| println!("{:08b}", w));
    for w in BitPermutations::new(4, 4) {
        println!("{:08b}", w);
    }
}