Function malachite_base::vecs::exhaustive::next_bit_pattern
source · pub fn next_bit_pattern(
pattern: &mut Vec<bool>,
bit_count: &mut usize,
min_bits: usize,
max_bits: usize,
)
Expand description
This function is used for iterating through all bit patterns with a specified number of minimum
and maximum true
bits.
Given an existing bit pattern, and a reference bit_count
, which must equal the number of
true
s in the pattern, mutates the pattern into the next pattern with a valid number of true
bits. See the unit tests for many examples.
§Worst-case complexity
$$ T(k) = O(k) $$
$$ M(k) = O(k) $$
where $T$ is time, $M$ is additional memory, and $k$ is the length of pattern
. The memory
usage is only linear when the pattern vector needs to be reallocated, which happens rarely.
§Panics
Panics if max_bits
is zero. (However, min_bits
may be zero.)
§Examples
use malachite_base::vecs::exhaustive::next_bit_pattern;
// Suppose we are generating all bit patterns with 2 to 4 true bits, inclusive. Suppose our
// current pattern is `1111000`. Then, the lexicographically next largest valid pattern is
// `10000001`. (All patterns of the form `1111xxx`, where the `x`s are not all zero, have too
// many ones. That brings us to `10000000`, which has too few ones, and then `10000001`.)
//
// The patterns are represented "in reverse", with least-significant bits appearing first.
let mut pattern = vec![false, false, false, true, true, true, true];
let mut bit_count = 4;
next_bit_pattern(&mut pattern, &mut bit_count, 2, 4);
assert_eq!(
pattern,
&[true, false, false, false, false, false, false, true]
);
assert_eq!(bit_count, 2);