Function malachite_base::vecs::exhaustive::next_bit_pattern

pub fn next_bit_pattern(
    pattern: &mut Vec<bool>,
    bit_count: &mut usize,
    min_bits: usize,
    max_bits: usize
)

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 trues 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);