Struct permutator::GosperCombinationIterator
source · [−]pub struct GosperCombinationIterator<'a, T> where
T: 'a, { /* private fields */ }
Expand description
Deprecated
This iterator family is now deprecated. Consider using LargeCombinationIterator instead. This is because current implementation need to copy every ref on every iteration which is inefficient. On uncontroll test environment, this iterator take 18.98s to iterate over 30,045,015 combinations. The LargeCombinationIterator took only 2.77s. If no more efficient implementation is available for some certain time period, this function will be officially mark with #[deprecated].
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] Here’s an example of code printing above combination.
use permutator::GosperCombinationIterator;
use std::time::{Instant};
let gosper = GosperCombinationIterator::new(&[1, 2, 3, 4, 5], 3);
let mut counter = 0;
let timer = Instant::now();
for combination in gosper {
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
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.
Total number of combinations this iterate can return. It will equals to n!/((n-r)!*r!)
Trait Implementations
type IntoIter = CombinationIterator<'a, T>
type IntoIter = CombinationIterator<'a, T>
Which kind of iterator are we turning this into?
fn into_iter(self) -> CombinationIterator<'a, T>ⓘNotable traits for CombinationIterator<'a, T>impl<'a, T> Iterator for CombinationIterator<'a, T> type Item = Vec<&'a T>;
fn into_iter(self) -> CombinationIterator<'a, T>ⓘNotable traits for CombinationIterator<'a, T>impl<'a, T> Iterator for CombinationIterator<'a, T> type Item = Vec<&'a T>;
impl<'a, T> Iterator for CombinationIterator<'a, T> type Item = Vec<&'a T>;
Creates an iterator from a value. Read more