[−][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

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

Github repository for more examples

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 `Iterator` trait so it can be used as `Iterator`. The struct provide into_iter() function that return itself.
CartesianProductIterator	Generate a cartesian product between given domains in an iterator style. The struct implement `Iterator` trait so it can be used in `Iterator` style. The struct provide into_iter() function that return itself.
CartesianProductRefIter	An unsafe way to generate a cartesian product between given domains into *mut [&T] in an iterator style. The struct implement `Iterator` trait so it can be used as `Iterator`. The struct provide into_iter() function that return itself.
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 `Iterator` trait.
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 `k` must be less than `n`. It'll attempt to permute given data by pick `k` elements out of `n` 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 by given Rc<RefCell<&mut [&T]>> parameter to new method of KPermutationCellIter.
KPermutationIterator	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.
KPermutationRefIter	k-Permutation over data of length "n" where `k` must be less than `n` and store result into mutable pointer. It'll attempt to permute given data by pick `k` elements out of `n` 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 by given *mut [&T]>> parameter to new method of KPermutationRefIter.
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 `collect` it.
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 `Iterator` trait so it can be used in `Iterator` style. The struct provide into_iter() function that return itself.
SelfCartesianProductIterator	Generate a cartesian product on itself in an iterator style. The struct implement `Iterator` trait so it can be used in `Iterator` style. The struct provide into_iter() function that return itself.
SelfCartesianProductRefIter	Generate a cartesian product on itself in an iterator style. The struct implement `Iterator` trait so it can be used in `Iterator` style. The struct provide into_iter() function that return itself.
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 `T`. For example,
Combination	Create a combination out of `T` Normally, it take a `[T]` or `Vec<T>` to create a combination.
IteratorReset	A trait that add reset function to an existing Iterator. It mean that the `next` or `next_into_cell` call will start returning the first element again
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 `Rc<RefCell<&mut [T]>>`.

Functions

cartesian_product	Create a cartesian product over given slice. The result will be a slice of borrowed `T`.
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 `objects` is [1, 2, 3] and degree is 2 then all possible result is [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]
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 `objects` is [1, 2, 3, 4] and `degree` is 2 then all possible permutation will be [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3].
get_permutation_size	Calculate all possible number of permutation. It's equals to size!/(size - 1).
heap_permutation	Heap permutation which permutate variable `d` in place and call `cb` function for each permutation done on `d`.
heap_permutation_cell	Heap permutation which permutate variable `d` in place and call `cb` function for each permutation done on `d`.
heap_permutation_sync	Heap permutation which permutate variable `d` in place and call `cb` function for each permutation done on `d`.
k_permutation	Generate k-permutation over slice of `d`. For example: d = &[1, 2, 3]; k = 2. The result will be [1, 2], [2, 1], [1, 3], [3, 1], [2, 3], [3, 2]
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 `T`.
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 `Permutation` trait to create k-permutation iterator from it.
KPermutationIntoRefParams	A tuple of 3 parameters that allow `Permutation` trait to create k-permutation ref iterator from it.
KPermutationParams	A pair of parameter that allow `Permutation` trait to create k-permutation iterator from it.
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.