Struct permutator::GosperCombination
source · pub struct GosperCombination<'a, T>where
T: 'a,{ /* private fields */ }
Expand description
Create a combination iterator. It use Gosper’s algorithm to pick a combination out of given data. The produced combination provide no lexicographic order.
The returned combination will be a reference into given data.
Each combination return from iterator will be a new Vec.
It’s safe to hold onto a combination or collect
it.
Examples
Given slice of [1, 2, 3, 4, 5]. It will produce following combinations: [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]
use permutator::GosperCombination;
use std::time::{Instant};
let gosper = GosperCombination::new(&[1, 2, 3, 4, 5], 3);
let mut counter = 0;
let timer = Instant::now();
for combination in gosper {
// uncomment a line below to print each combination
// println!("{}:{:?}", counter, combination);
counter += 1;
}
println!("Total {} combinations in {:?}", counter, timer.elapsed());
Limitation
Gosper algorithm need to know the MSB (most significant bit). The current largest known MSB data type is u128. This make the implementation support up to 128 elements slice.
See
Implementations
sourceimpl<'a, T> GosperCombination<'a, T>
impl<'a, T> GosperCombination<'a, T>
sourcepub fn new(data: &[T], r: usize) -> GosperCombination<'_, T>
pub fn new(data: &[T], r: usize) -> GosperCombination<'_, T>
Create new combination generator using Gosper’s algorithm.
r
shall be smaller than data.len().
Note: It perform no check on given parameter. If r is larger than length of data then iterate over it will not occur. The iteration will be end upon enter.
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Total number of combinations this iterate can return. It will equals to n!/((n-r)!*r!)
sourcepub fn next(&mut self, result: &mut [&'a T]) -> Option<()>
pub fn next(&mut self, result: &mut [&'a T]) -> Option<()>
Attempt to get next combination and mutate a given
result
to store the next combination.
This function mimic Iterator’s next style.
It’ll return an empty Option because result will be
contain in given paramter.
It return None
when there’s no further possible combination.
sourcepub fn next_into_cell(
&mut self,
result: &Rc<RefCell<&mut [&'a T]>>
) -> Option<()>
pub fn next_into_cell(
&mut self,
result: &Rc<RefCell<&mut [&'a T]>>
) -> Option<()>
Attempt to get next combination and store it into Rc<RefCell<>>
of mutable slice result
to store the next combination.
This function mimic Iterator’s next style.
It’ll return an empty Option because result will be
contain in given paramter.
It return None
when there’s no further possible combination.
Use this function when you want a faster than copy/clone but need to share the combination to multiple target.
The test in uncontrol environment found that using this function yield performance on par with combination_cell function.