Skip to content

Instantly share code, notes, and snippets.

@m1el
Last active November 24, 2022 13:01
Show Gist options
  • Save m1el/6016b53ff20ae08712436a4b073820f2 to your computer and use it in GitHub Desktop.
Save m1el/6016b53ff20ae08712436a4b073820f2 to your computer and use it in GitHub Desktop.
// 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}}
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");
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 suffix = suffix_mask & current;
let next_bit_mask = suffix_mask.wrapping_add(1);
let next_bit_m1 = (next_bit_mask & current).wrapping_sub(1);
current = current + suffix - next_bit_m1;
}
}
struct BitPermutations {
limit_mask: u64,
current: u64,
}
impl BitPermutations {
pub fn new(zeros: u32, ones: u32) -> Self {
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).wrapping_sub(1);
self.current = current + suffix - next_bit_m1;
Some(current)
}
}
fn main() {
visit_combinations(4, 4, |w| println!("{:08b}", w));
for w in BitPermutations::new(4, 4) {
println!("{:08b}", w);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment