Struct permutator::XPermutationIterator
source · pub struct XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a,{ /* private fields */ }
Expand description
A lexicographic ordered permutation based on “Algoritm X” published by Donald E. Knuth. page 20.
If order is not important, consider using heap permutation struct instead. This struct is a bit slower (about 10%) than heap permutation in uncontroll test environment.
The algorithm work by simulate tree traversal where some branch can be
skip altogether. This is archive by provided t
function that take
slice of partial result as parameter. If the partial result needed to be skip,
return false. Otherwise, return true and the algorithm will call this function
again when the branch is descended deeper. For example: First call to t
may
contain [1]. If t
return true, it will be called again with [1, 2]. If it
return true, and there’s leaf node, cb will be called with [1, 2]. On the other hand,
if t
is called with [1, 3] and it return false, it won’t call the callback.
If t
is called with [4] and it return false, it won’t try to traverse deeper even
if there’re [4, 5], or [4, 6]. It will skip altogether and call t
with [7].
The process goes on until every branch is traversed.
Example
Get all lexicalgraphic ordered permutation
use permutator::XPermutationIterator;
let data = vec![1, 2, 3, 4];
let mut counter = 0;
XPermutationIterator::new(&data, |_| true).for_each(|p| {
println!("{:?}", p);
counter += 1;
});
assert_eq!(factorial(data.len()), counter);
Skip all permutation that has 1
in first element.
use permutator::XPermutationIterator;
let data : Vec<u8> = vec![1, 2, 3, 4];
let mut counter = 0;
XPermutationIterator::new(&data, |f| {
*f[0] != 1u8 // filter all permutation that start with 1
}).for_each(|p| {
println!("{:?}", p);
counter += 1;
});
assert_eq!(factorial(data.len()) - factorial(data.len() - 1), counter);
Multi-threads permutation example
use permutator::XpermutationIterator;
use std::time::{Instant};
let data : Vec<usize> = (0..4).map(|num| num).collect();
let threads = 2;
let chunk = data.len() / threads;
let (tx, rx) = mpsc::channel();
for i in 0..threads {
let start = chunk * i;
let end = match i {
j if j == threads - 1 => data.len(), // last thread handle remaining work
_ => chunk * (i + 1)
};
let l_dat = data.to_owned(); // copy data for each thread
let end_sig = tx.clone();
thread::spawn(move || {
let timer = Instant::now();
let perm = XPermutationIterator::new(
&l_dat,
|v| *v[0] >= start && *v[0] < end // skip branch that is outside the start/end
);
let mut counter = 0u64;
for p in perm {
// each permutation is stored in p
counter += 1;
}
end_sig.send(i).unwrap();
});
}
let main = thread::spawn(move || { // main thread
let mut counter = 0;
while counter < threads {
let i = rx.recv().unwrap();
// do something
counter += 1;
}
});
main.join().unwrap();
Implementations
sourceimpl<'a, F, T> XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a,
impl<'a, F, T> XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a,
sourcepub fn new(data: &'a [T], t: F) -> XPermutationIterator<'_, F, T>ⓘNotable traits for XPermutationIterator<'a, F, T>impl<'a, F, T> Iterator for XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a, type Item = Vec<&'a T>;
pub fn new(data: &'a [T], t: F) -> XPermutationIterator<'_, F, T>ⓘNotable traits for XPermutationIterator<'a, F, T>impl<'a, F, T> Iterator for XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a, type Item = Vec<&'a T>;
F: FnMut(&[&T]) -> bool,
T: 'a, type Item = Vec<&'a T>;
Construct new XPermutationIterator object.
Parameters
data : &[T]
- A data used for generate permutation.t : FnMut(&[&T])
- A function that if return true, will make algorithm continue traversing the tree. Otherwise, the entire branch will be skip.
Trait Implementations
sourceimpl<'a, F, T> ExactSizeIterator for XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a,
impl<'a, F, T> ExactSizeIterator for XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a,
sourceimpl<'a, F, T> Iterator for XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a,
impl<'a, F, T> Iterator for XPermutationIterator<'a, F, T>where
F: FnMut(&[&T]) -> bool,
T: 'a,
sourcefn next(&mut self) -> Option<Self::Item>
fn next(&mut self) -> Option<Self::Item>
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
)