[−][src]Crate permutator
This crate provide generic cartesian product iterator, combination iterator, and permutation iterator.
Three main functionalities
- Cartesian product
- Combination
- Permutation
Two different style on every functionality
This crate provide two implementation style
- Iterator style
- Callback function style
Easily share result
- Every functionalities can take Rc<RefCell<>> to store result.
- An iterator that return owned value.
- Every callback style function can take Arc<RwLock<>> to store result.
Easy usage
Three built-in traits that add cart_prod, combination, and permutation functionality to slice/array, Rc<RefCell<&mut[T]>>, and more.
Unreach raw performance with unsafe
Every functionalities can take raw mutable pointer to store result.
Example
- Getting k-permutation where k is 3 and n is 5.
use permutator::{Combination, Permutation}; let mut data = &[1, 2, 3, 4, 5]; let mut counter = 1; data.combination(3).for_each(|mut c| { c.permutation().for_each(|p| { println!("k-permutation@{}={:?}", counter, p); counter += 1; }); });
- Getting lexicographically ordered k-permutation where k is 3 and n is 5.
use permutator::{Combination, XPermutationIterator}; let mut data = &[1, 2, 3, 4, 5]; let mut counter = 1; data.combination(3).for_each(|mut c| { XPermutationIterator::new(&c, |_| true).for_each(|p| { println!("k-permutation@{}={:?}", counter, p); counter += 1; }); });
- Cartesian product of set of 3, 4, and 5 respectively
use permutator::{CartesianProductIterator, cartesian_product}; let mut domains : &[&[i32]]= &[&[1, 2], &[3, 4, 5], &[6, 7, 8, 9]]; println!("=== Cartesian product iterative style ==="); CartesianProductIterator::new(domains).into_iter().for_each(|p| { println!("{:?}", p); }); println!("=== cartesian product callback style ==="); cartesian_product(domains, |p| { // `p` is borrowed a ref to internal variable inside cartesian_product function. println!("{:?}", p); });
- Easy sharable result
use std::cell::RefCell; use std::rc::Rc; use std::time::Instant; use permutator::CartesianProduct; let mut counter = 0; let timer = Instant::now(); let data : &[&[u8]]= &[&[1, 2], &[3, 4, 5, 6], &[7, 8, 9]]; let mut result = vec![&data[0][0]; data.len()]; let shared = Rc::new(RefCell::new(result.as_mut_slice())); (data, Rc::clone(&shared)).cart_prod().for_each(|_| { println!("{:?}", &*shared.borrow()); // and notify result borrower(s) that new product is available. counter += 1; }); println!("Total {} products done in {:?}", counter, timer.elapsed());
- Unsafely share result example
use std::time::Instant; use permutator::Permutation; let data : &[i32] = &[1, 2, 3, 4, 5]; let mut counter = 0; let k = 3; let mut result : Vec<&i32> = vec![&data[0]; k]; // `result` can be share safely anywhere let shared = result.as_mut_slice() as *mut [&i32]; // `shared` can be share as long as `result` is alive let timer = Instant::now(); // unsafe statement may be omit because the permutation trait // hid it internally. However, keep in mind that it rely // on a pointer so every operation is still considered unsafe. unsafe { (data, k, shared).permutation().for_each(|_| { println!("{:?}", &*shared); // and notify result borrower(s) that new permutation is available. counter += 1; }); println!("Total {} combination done in {:?}", counter, timer.elapsed()); }
See
Found a bug ?
Open issue at Github
Modules
copy | A module that perform everything in copy fashion. There is no Heap permutation family function in here because that function family already return a slice of value. |
Structs
CartesianProductCellIter | Generate a cartesian product between given domains into Rc<RefCell<&mut [&T]>>
in an iterator style.
The struct implement |
CartesianProductIterator | Generate a cartesian product between given domains in an iterator style.
The struct implement |
CartesianProductRefIter | An unsafe way to generate a cartesian product between given domains
into *mut [&T] in an iterator style.
The struct implement |
CombinationCellIter | Deprecated |
CombinationIterator | Deprecated |
CombinationRefIter | Deprecated |
GosperCombinationCellIter | Deprecated |
GosperCombinationIterator | Deprecated |
GosperCombinationRefIter | Deprecated |
HeapPermutationCellIter | Heap's permutation in Rc<RefCell<>> mimic Iterator style.
It provides another choice for user that want to share
permutation result but doesn't want to clone it for
each share. It also doesn't create new result on each
iteration unlike other object that implement |
HeapPermutationIterator | Heap's permutation in iterator style implementation. |
HeapPermutationRefIter | An unsafe Heap's permutation in iterator style implementation. |
KPermutationCellIter | k-Permutation over data of length "n" where |
KPermutationIterator | k-Permutation over data of length n where k must be
less than n.
It'll attempt to permute given data by pick |
KPermutationRefIter | k-Permutation over data of length "n" where |
LargeCombinationCellIter | Create a combination iterator. The result is lexicographic ordered if input is lexicorgraphic ordered. The returned combination will be a reference into given data. Each combination return from iterator is stored into given Rc<RefCell<&mut [&T]>>. |
LargeCombinationIterator | Create a combination iterator.
The result is lexicographic ordered if input is lexicorgraphic ordered.
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 |
LargeCombinationRefIter | Create an unsafe combination iterator that return result to mutable pointer. The result is lexicographic ordered if input is lexicorgraphic ordered. The returned combination will be a reference into given data. Each combination return from iterator is stored into given *mut [&T]. |
SelfCartesianProductCellIter | Generate a cartesian product on itself in an iterator style.
The struct implement |
SelfCartesianProductIterator | Generate a cartesian product on itself in an iterator style.
The struct implement |
SelfCartesianProductRefIter | Generate a cartesian product on itself in an iterator style.
The struct implement |
XPermutationCellIter | A lexicographic ordered permutation based on "Algoritm X" published by Donald E. Knuth. page 20. |
XPermutationIterator | A lexicographic ordered permutation based on "Algoritm X" published by Donald E. Knuth. page 20. |
XPermutationRefIter | A lexicographic ordered permutation based on "Algoritm X" published by Donald E. Knuth. page 20. |
Traits
CartesianProduct | Create a cartesian product out of |
Combination | Create a combination out of |
IteratorReset | A trait that add reset function to an existing Iterator.
It mean that the |
Permutation | Create a permutation iterator that permute data in place.
Built-in implementation return an object of
HeapPermutation for slice/array and Vec.
It return an object of HeapPermutationCellIter
on data type of |
Functions
cartesian_product | Create a cartesian product over given slice. The result will be a slice
of borrowed |
cartesian_product_cell | Similar to safe cartesian_product function except the way it return the product. It return result through Rc<RefCell<>> to mutable slice of result. It'll notify caller on each new result via empty callback function. |
cartesian_product_sync | Similar to safe cartesian_product function except the way it return the product. It return result through Rc<RefCell<>> to mutable slice of result. It'll notify caller on each new result via empty callback function. |
combination | Deprecated |
combination_cell | Deprecated |
combination_sync | Deprecated |
divide_factorial | Calculate factorial for two factorial division. It'll return 1 if numerator is smaller or equals to denominator. Otherwise, it'll short circuit the calculation by calculate only the undivided remainder. |
factorial | Calculate factorial from given value. |
get_cartesian_for | Get a cartesian product at specific location.
If |
get_cartesian_size | Calculate all possible cartesian combination size. It is always equals to size.pow(degree). |
get_permutation_for | Get permutation at specific location.
If |
get_permutation_size | Calculate all possible number of permutation. It's equals to size!/(size - 1). |
heap_permutation | Heap permutation which permutate variable |
heap_permutation_cell | Heap permutation which permutate variable |
heap_permutation_sync | Heap permutation which permutate variable |
k_permutation | Generate k-permutation over slice of |
k_permutation_cell | Similar to safe k_permutation function except the way it return the permutation. It return result through mutable pointer to result assuming the pointer is valid. It'll notify caller on each new result via empty callback function. |
k_permutation_sync | Similar to safe k_permutation function except the way it return the permutation. It return result through mutable pointer to result assuming the pointer is valid. It'll notify caller on each new result via empty callback function. |
large_combination | Generate a r-combination from given domain and call callback function on each combination. |
large_combination_cell | Generate a r-combination from given domain and call callback function on each combination. The result will be return into Rc<RefCell<>>. |
large_combination_sync | Generate a r-combination from given domain and call callback function on each combination. The result will be return into Arc<RwLock<>>. |
multiply_factorial | Calculate two factorial multiply on each other. It'll try to reduce calculation time by calculate the common value only once. |
self_cartesian_product | Create a cartesian product over itself. The result will be a slice
of borrowed |
self_cartesian_product_cell | Similar to safe cartesian_product function except the way it return the product. It return result through Rc<RefCell<>> to mutable slice of result. It'll notify caller on each new result via empty callback function. |
self_cartesian_product_sync | Similar to safe self_cartesian_product function except the way it return the product. It return result through Arc<RwLock<>> to mutable slice of result. It'll notify caller on each new result via empty callback function. |
unsafe_cartesian_product⚠ | Similar to safe cartesian_product function except the way it return the product. It return result through mutable pointer to result assuming the pointer is valid. It'll notify caller on each new result via empty callback function. |
unsafe_combination⚠ | Deprecated |
unsafe_k_permutation⚠ | Similar to safe k_permutation function except the way it return the permutation. It return result through mutable pointer to result assuming the pointer is valid. It'll notify caller on each new result via empty callback function. |
unsafe_large_combination⚠ | Generate a r-combination from given domain and call callback function on each combination. The result will be return into ref mut pointer. |
unsafe_self_cartesian_product⚠ | Similar to safe self_cartesian_product function except the way it return the product. It return result through mutable pointer to result assuming the pointer is valid. It'll notify caller on each new result via empty callback function. |
unsafe_x_permutation⚠ | A lexicographic ordered permutation based on "Algoritm X" published by Donald E. Knuth. page 20. |
x_permutation | A lexicographic ordered permutation based on "Algoritm X" published by Donald E. Knuth. page 20. |
x_permutation_cell | A lexicographic ordered permutation based on "Algoritm X" published by Donald E. Knuth. page 20. |
x_permutation_sync | A lexicographic ordered permutation based on "Algoritm X" published by Donald E. Knuth. page 20. |
Type Definitions
CartesianProductIntoCellParams | A type that represent a cartesian product of the slice over slices and return result into Rc<RefCell<&mut [&T]>> by using CartesianProductCellIter |
CartesianProductIntoRefParams | A type that used exclusively for trait CartesianProduct. It return CartesianProductRefIter. |
CombinationIntoCellParams | A pair of source and sink to get a sharable combination. |
CombinationIntoRefParams | A pair of source and sink to get a sharable combination. |
KPermutationIntoCellParams | A tuples of 3 parameters that allow |
KPermutationIntoRefParams | A tuple of 3 parameters that allow |
KPermutationParams | A pair of parameter that allow |
SelfCartesianProduct | A type that used exclusively for trait CartesianProduct. It return SelfCartesianProductIterator. |
SelfCartesianProductIntoCellParams | A type that used exclusively for trait CartesianProduct. It return SelfCartesianProductCellIter. |
SelfCartesianProductIntoRefParams | A type that used exclusively for trait CartesianProduct. It return SelfCartesianProductRefIter. |