Struct permutator::KPermutationIterator
source · pub struct KPermutationIterator<'a, T>where
T: 'a,{ /* private fields */ }
Expand description
k-Permutation over data of length n where k must be
less than n.
It’ll attempt to permute given data by pick k
elements
out of data. It use Gosper algorithm to pick the elements.
It then use Heap’s algorithm to permute those k
elements
and return each permutation back to caller.
Examples
- Iterator style permit using ‘for-in’ style loop along with enable usage of functional paradigm over iterator object.
use permutator::KPermutationIterator;
use std::time::Instant;
let data = [1, 2, 3, 4, 5];
let permutator = KPermutationIterator::new(&data, 3);
let mut counter = 0;
// println!("Begin testing KPermutation");
let timer = Instant::now();
for permuted in permutator {
// uncomment a line below to print all permutation.
// println!("{}:{:?}", counter, permuted);
counter += 1;
}
// Or simply use functional paradigm of iterator like below
// permutator.into_iter().any(|item| {item == [7, 8, 9]});
println!("Total {} permutations done in {:?}", counter, timer.elapsed());
assert_eq!(60, counter);
Notes
The additional functionality provided by this struct is that it can be pause or completely stop midway while the k-permutation need to be run from start to finish only.
Safety
This struct implementation use unsafe code internally.
It use unsafe because it uses Vec<T>
to own a combination
for each permutation. Rust cannot derive lifetime of mutable
slice created inside next and store it into struct object itself.
This is because next
signature have no lifetime associated
with self
. To get around this, the implementation convert
Vec*mut [T]
then perform &mut *
on it.
See
Implementations
sourceimpl<'a, T> KPermutationIterator<'a, T>
impl<'a, T> KPermutationIterator<'a, T>
Trait Implementations
sourceimpl<'a, T> ExactSizeIterator for KPermutationIterator<'a, T>
impl<'a, T> ExactSizeIterator for KPermutationIterator<'a, T>
sourceimpl<'a, T> Iterator for KPermutationIterator<'a, T>
impl<'a, T> Iterator for KPermutationIterator<'a, T>
sourcefn next(&mut self) -> Option<Vec<&'a T>>
fn next(&mut self) -> Option<Vec<&'a T>>
sourcefn next_chunk<const N: usize>(
&mut self
) -> Result<[Self::Item; N], IntoIter<Self::Item, N>>where
Self: Sized,
fn next_chunk<const N: usize>(
&mut self
) -> Result<[Self::Item; N], IntoIter<Self::Item, N>>where
Self: Sized,
iter_next_chunk
)N
values. Read more1.0.0 · sourcefn size_hint(&self) -> (usize, Option<usize>)
fn size_hint(&self) -> (usize, Option<usize>)
1.0.0 · sourcefn count(self) -> usizewhere
Self: Sized,
fn count(self) -> usizewhere
Self: Sized,
1.0.0 · sourcefn last(self) -> Option<Self::Item>where
Self: Sized,
fn last(self) -> Option<Self::Item>where
Self: Sized,
sourcefn advance_by(&mut self, n: usize) -> Result<(), usize>
fn advance_by(&mut self, n: usize) -> Result<(), usize>
iter_advance_by
)n
elements. Read more1.0.0 · sourcefn nth(&mut self, n: usize) -> Option<Self::Item>
fn nth(&mut self, n: usize) -> Option<Self::Item>
n
th element of the iterator. Read more1.28.0 · sourcefn step_by(self, step: usize) -> StepBy<Self>where
Self: Sized,
fn step_by(self, step: usize) -> StepBy<Self>where
Self: Sized,
1.0.0 · sourcefn chain<U>(self, other: U) -> Chain<Self, <U as IntoIterator>::IntoIter>where
Self: Sized,
U: IntoIterator<Item = Self::Item>,
fn chain<U>(self, other: U) -> Chain<Self, <U as IntoIterator>::IntoIter>where
Self: Sized,
U: IntoIterator<Item = Self::Item>,
1.0.0 · sourcefn zip<U>(self, other: U) -> Zip<Self, <U as IntoIterator>::IntoIter>where
Self: Sized,
U: IntoIterator,
fn zip<U>(self, other: U) -> Zip<Self, <U as IntoIterator>::IntoIter>where
Self: Sized,
U: IntoIterator,
sourcefn intersperse_with<G>(self, separator: G) -> IntersperseWith<Self, G>where
Self: Sized,
G: FnMut() -> Self::Item,
fn intersperse_with<G>(self, separator: G) -> IntersperseWith<Self, G>where
Self: Sized,
G: FnMut() -> Self::Item,
iter_intersperse
)separator
between adjacent items of the original iterator. Read more1.0.0 · sourcefn map<B, F>(self, f: F) -> Map<Self, F>where
Self: Sized,
F: FnMut(Self::Item) -> B,
fn map<B, F>(self, f: F) -> Map<Self, F>where
Self: Sized,
F: FnMut(Self::Item) -> B,
1.21.0 · sourcefn for_each<F>(self, f: F)where
Self: Sized,
F: FnMut(Self::Item),
fn for_each<F>(self, f: F)where
Self: Sized,
F: FnMut(Self::Item),
1.0.0 · sourcefn filter<P>(self, predicate: P) -> Filter<Self, P>where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
fn filter<P>(self, predicate: P) -> Filter<Self, P>where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
1.0.0 · sourcefn filter_map<B, F>(self, f: F) -> FilterMap<Self, F>where
Self: Sized,
F: FnMut(Self::Item) -> Option<B>,
fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F>where
Self: Sized,
F: FnMut(Self::Item) -> Option<B>,
1.0.0 · sourcefn enumerate(self) -> Enumerate<Self>where
Self: Sized,
fn enumerate(self) -> Enumerate<Self>where
Self: Sized,
1.0.0 · sourcefn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P>where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P>where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
1.0.0 · sourcefn take_while<P>(self, predicate: P) -> TakeWhile<Self, P>where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P>where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
1.57.0 · sourcefn map_while<B, P>(self, predicate: P) -> MapWhile<Self, P>where
Self: Sized,
P: FnMut(Self::Item) -> Option<B>,
fn map_while<B, P>(self, predicate: P) -> MapWhile<Self, P>where
Self: Sized,
P: FnMut(Self::Item) -> Option<B>,
1.0.0 · sourcefn skip(self, n: usize) -> Skip<Self>where
Self: Sized,
fn skip(self, n: usize) -> Skip<Self>where
Self: Sized,
n
elements. Read more1.0.0 · sourcefn take(self, n: usize) -> Take<Self>where
Self: Sized,
fn take(self, n: usize) -> Take<Self>where
Self: Sized,
n
elements, or fewer
if the underlying iterator ends sooner. Read more1.0.0 · sourcefn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>where
Self: Sized,
F: FnMut(&mut St, Self::Item) -> Option<B>,
fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>where
Self: Sized,
F: FnMut(&mut St, Self::Item) -> Option<B>,
1.0.0 · sourcefn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>where
Self: Sized,
U: IntoIterator,
F: FnMut(Self::Item) -> U,
fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>where
Self: Sized,
U: IntoIterator,
F: FnMut(Self::Item) -> U,
1.0.0 · sourcefn inspect<F>(self, f: F) -> Inspect<Self, F>where
Self: Sized,
F: FnMut(&Self::Item),
fn inspect<F>(self, f: F) -> Inspect<Self, F>where
Self: Sized,
F: FnMut(&Self::Item),
1.0.0 · sourcefn by_ref(&mut self) -> &mut Selfwhere
Self: Sized,
fn by_ref(&mut self) -> &mut Selfwhere
Self: Sized,
1.0.0 · sourcefn collect<B>(self) -> Bwhere
B: FromIterator<Self::Item>,
Self: Sized,
fn collect<B>(self) -> Bwhere
B: FromIterator<Self::Item>,
Self: Sized,
sourcefn collect_into<E>(self, collection: &mut E) -> &mut Ewhere
E: Extend<Self::Item>,
Self: Sized,
fn collect_into<E>(self, collection: &mut E) -> &mut Ewhere
E: Extend<Self::Item>,
Self: Sized,
iter_collect_into
)1.0.0 · sourcefn partition<B, F>(self, f: F) -> (B, B)where
Self: Sized,
B: Default + Extend<Self::Item>,
F: FnMut(&Self::Item) -> bool,
fn partition<B, F>(self, f: F) -> (B, B)where
Self: Sized,
B: Default + Extend<Self::Item>,
F: FnMut(&Self::Item) -> bool,
sourcefn is_partitioned<P>(self, predicate: P) -> boolwhere
Self: Sized,
P: FnMut(Self::Item) -> bool,
fn is_partitioned<P>(self, predicate: P) -> boolwhere
Self: Sized,
P: FnMut(Self::Item) -> bool,
iter_is_partitioned
)true
precede all those that return false
. Read more1.27.0 · sourcefn try_fold<B, F, R>(&mut self, init: B, f: F) -> Rwhere
Self: Sized,
F: FnMut(B, Self::Item) -> R,
R: Try<Output = B>,
fn try_fold<B, F, R>(&mut self, init: B, f: F) -> Rwhere
Self: Sized,
F: FnMut(B, Self::Item) -> R,
R: Try<Output = B>,
1.27.0 · sourcefn try_for_each<F, R>(&mut self, f: F) -> Rwhere
Self: Sized,
F: FnMut(Self::Item) -> R,
R: Try<Output = ()>,
fn try_for_each<F, R>(&mut self, f: F) -> Rwhere
Self: Sized,
F: FnMut(Self::Item) -> R,
R: Try<Output = ()>,
1.0.0 · sourcefn fold<B, F>(self, init: B, f: F) -> Bwhere
Self: Sized,
F: FnMut(B, Self::Item) -> B,
fn fold<B, F>(self, init: B, f: F) -> Bwhere
Self: Sized,
F: FnMut(B, Self::Item) -> B,
1.51.0 · sourcefn reduce<F>(self, f: F) -> Option<Self::Item>where
Self: Sized,
F: FnMut(Self::Item, Self::Item) -> Self::Item,
fn reduce<F>(self, f: F) -> Option<Self::Item>where
Self: Sized,
F: FnMut(Self::Item, Self::Item) -> Self::Item,
sourcefn try_reduce<F, R>(
&mut self,
f: F
) -> <<R as Try>::Residual as Residual<Option<<R as Try>::Output>>>::TryTypewhere
Self: Sized,
F: FnMut(Self::Item, Self::Item) -> R,
R: Try<Output = Self::Item>,
<R as Try>::Residual: Residual<Option<Self::Item>>,
fn try_reduce<F, R>(
&mut self,
f: F
) -> <<R as Try>::Residual as Residual<Option<<R as Try>::Output>>>::TryTypewhere
Self: Sized,
F: FnMut(Self::Item, Self::Item) -> R,
R: Try<Output = Self::Item>,
<R as Try>::Residual: Residual<Option<Self::Item>>,
iterator_try_reduce
)1.0.0 · sourcefn all<F>(&mut self, f: F) -> boolwhere
Self: Sized,
F: FnMut(Self::Item) -> bool,
fn all<F>(&mut self, f: F) -> boolwhere
Self: Sized,
F: FnMut(Self::Item) -> bool,
1.0.0 · sourcefn any<F>(&mut self, f: F) -> boolwhere
Self: Sized,
F: FnMut(Self::Item) -> bool,
fn any<F>(&mut self, f: F) -> boolwhere
Self: Sized,
F: FnMut(Self::Item) -> bool,
1.0.0 · sourcefn find<P>(&mut self, predicate: P) -> Option<Self::Item>where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
fn find<P>(&mut self, predicate: P) -> Option<Self::Item>where
Self: Sized,
P: FnMut(&Self::Item) -> bool,
1.30.0 · sourcefn find_map<B, F>(&mut self, f: F) -> Option<B>where
Self: Sized,
F: FnMut(Self::Item) -> Option<B>,
fn find_map<B, F>(&mut self, f: F) -> Option<B>where
Self: Sized,
F: FnMut(Self::Item) -> Option<B>,
sourcefn try_find<F, R>(
&mut self,
f: F
) -> <<R as Try>::Residual as Residual<Option<Self::Item>>>::TryTypewhere
Self: Sized,
F: FnMut(&Self::Item) -> R,
R: Try<Output = bool>,
<R as Try>::Residual: Residual<Option<Self::Item>>,
fn try_find<F, R>(
&mut self,
f: F
) -> <<R as Try>::Residual as Residual<Option<Self::Item>>>::TryTypewhere
Self: Sized,
F: FnMut(&Self::Item) -> R,
R: Try<Output = bool>,
<R as Try>::Residual: Residual<Option<Self::Item>>,
try_find
)1.0.0 · sourcefn position<P>(&mut self, predicate: P) -> Option<usize>where
Self: Sized,
P: FnMut(Self::Item) -> bool,
fn position<P>(&mut self, predicate: P) -> Option<usize>where
Self: Sized,
P: FnMut(Self::Item) -> bool,
1.6.0 · sourcefn max_by_key<B, F>(self, f: F) -> Option<Self::Item>where
B: Ord,
Self: Sized,
F: FnMut(&Self::Item) -> B,
fn max_by_key<B, F>(self, f: F) -> Option<Self::Item>where
B: Ord,
Self: Sized,
F: FnMut(&Self::Item) -> B,
1.15.0 · sourcefn max_by<F>(self, compare: F) -> Option<Self::Item>where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
fn max_by<F>(self, compare: F) -> Option<Self::Item>where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
1.6.0 · sourcefn min_by_key<B, F>(self, f: F) -> Option<Self::Item>where
B: Ord,
Self: Sized,
F: FnMut(&Self::Item) -> B,
fn min_by_key<B, F>(self, f: F) -> Option<Self::Item>where
B: Ord,
Self: Sized,
F: FnMut(&Self::Item) -> B,
1.15.0 · sourcefn min_by<F>(self, compare: F) -> Option<Self::Item>where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
fn min_by<F>(self, compare: F) -> Option<Self::Item>where
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
1.0.0 · sourcefn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB)where
FromA: Default + Extend<A>,
FromB: Default + Extend<B>,
Self: Sized + Iterator<Item = (A, B)>,
fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB)where
FromA: Default + Extend<A>,
FromB: Default + Extend<B>,
Self: Sized + Iterator<Item = (A, B)>,
1.36.0 · sourcefn copied<'a, T>(self) -> Copied<Self>where
T: 'a + Copy,
Self: Sized + Iterator<Item = &'a T>,
fn copied<'a, T>(self) -> Copied<Self>where
T: 'a + Copy,
Self: Sized + Iterator<Item = &'a T>,
1.0.0 · sourcefn cloned<'a, T>(self) -> Cloned<Self>where
T: 'a + Clone,
Self: Sized + Iterator<Item = &'a T>,
fn cloned<'a, T>(self) -> Cloned<Self>where
T: 'a + Clone,
Self: Sized + Iterator<Item = &'a T>,
sourcefn array_chunks<const N: usize>(self) -> ArrayChunks<Self, N>where
Self: Sized,
fn array_chunks<const N: usize>(self) -> ArrayChunks<Self, N>where
Self: Sized,
iter_array_chunks
)N
elements of the iterator at a time. Read more1.11.0 · sourcefn sum<S>(self) -> Swhere
Self: Sized,
S: Sum<Self::Item>,
fn sum<S>(self) -> Swhere
Self: Sized,
S: Sum<Self::Item>,
1.11.0 · sourcefn product<P>(self) -> Pwhere
Self: Sized,
P: Product<Self::Item>,
fn product<P>(self) -> Pwhere
Self: Sized,
P: Product<Self::Item>,
sourcefn cmp_by<I, F>(self, other: I, cmp: F) -> Orderingwhere
Self: Sized,
I: IntoIterator,
F: FnMut(Self::Item, <I as IntoIterator>::Item) -> Ordering,
fn cmp_by<I, F>(self, other: I, cmp: F) -> Orderingwhere
Self: Sized,
I: IntoIterator,
F: FnMut(Self::Item, <I as IntoIterator>::Item) -> Ordering,
iter_order_by
)Iterator
with those
of another with respect to the specified comparison function. Read more1.5.0 · sourcefn partial_cmp<I>(self, other: I) -> Option<Ordering>where
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
fn partial_cmp<I>(self, other: I) -> Option<Ordering>where
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
sourcefn partial_cmp_by<I, F>(self, other: I, partial_cmp: F) -> Option<Ordering>where
Self: Sized,
I: IntoIterator,
F: FnMut(Self::Item, <I as IntoIterator>::Item) -> Option<Ordering>,
fn partial_cmp_by<I, F>(self, other: I, partial_cmp: F) -> Option<Ordering>where
Self: Sized,
I: IntoIterator,
F: FnMut(Self::Item, <I as IntoIterator>::Item) -> Option<Ordering>,
iter_order_by
)Iterator
with those
of another with respect to the specified comparison function. Read more1.5.0 · sourcefn eq<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialEq<<I as IntoIterator>::Item>,
Self: Sized,
fn eq<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialEq<<I as IntoIterator>::Item>,
Self: Sized,
sourcefn eq_by<I, F>(self, other: I, eq: F) -> boolwhere
Self: Sized,
I: IntoIterator,
F: FnMut(Self::Item, <I as IntoIterator>::Item) -> bool,
fn eq_by<I, F>(self, other: I, eq: F) -> boolwhere
Self: Sized,
I: IntoIterator,
F: FnMut(Self::Item, <I as IntoIterator>::Item) -> bool,
iter_order_by
)1.5.0 · sourcefn ne<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialEq<<I as IntoIterator>::Item>,
Self: Sized,
fn ne<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialEq<<I as IntoIterator>::Item>,
Self: Sized,
1.5.0 · sourcefn lt<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
fn lt<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
Iterator
are lexicographically
less than those of another. Read more1.5.0 · sourcefn le<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
fn le<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
Iterator
are lexicographically
less or equal to those of another. Read more1.5.0 · sourcefn gt<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
fn gt<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
Iterator
are lexicographically
greater than those of another. Read more1.5.0 · sourcefn ge<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
fn ge<I>(self, other: I) -> boolwhere
I: IntoIterator,
Self::Item: PartialOrd<<I as IntoIterator>::Item>,
Self: Sized,
Iterator
are lexicographically
greater than or equal to those of another. Read moresourcefn is_sorted_by<F>(self, compare: F) -> boolwhere
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>,
fn is_sorted_by<F>(self, compare: F) -> boolwhere
Self: Sized,
F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>,
is_sorted
)sourcefn is_sorted_by_key<F, K>(self, f: F) -> boolwhere
Self: Sized,
F: FnMut(Self::Item) -> K,
K: PartialOrd<K>,
fn is_sorted_by_key<F, K>(self, f: F) -> boolwhere
Self: Sized,
F: FnMut(Self::Item) -> K,
K: PartialOrd<K>,
is_sorted
)