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

Easy share result

• Every function 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

Two built-in traits that add combination and permutation functionality to both Vec and slice.

Unreach raw performance with unsafe

Every callback style function 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;
    });
});

• Cartesian product of set of 3, 4, and 5 respectively

use permutator::{CartesianProduct, cartesian_product};
let mut domains : &[&[i32]]= &[&[1, 2], &[3, 4, 5], &[6, 7, 8, 9]];
println!("=== Cartesian product iterative style ===");
CartesianProduct::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);
});

See

• Github repository for more examples

Structs

CartesianProduct

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.

CombinationIterator

An iterator return from struct GosperCombination or from trait Combination over slice or vec of data.

GosperCombination

Create a combination iterator. It use Gosper’s algorithm to pick a combination out of given data. The produced combination provide no lexicographic order.

HeapPermutation

Heap’s permutation in iterator style implementation. It provide two way to iterate over the permutation.

KPermutation

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.

Traits

Combination

Create a combination out of T Normally, it take a [T] or Vec<T> to create a combination.

Permutation

Create a permutation iterator that permute data in place. It return an object of HeapPermutation which can be used as iterator or manual iterate for higher throughput.

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

Generate a combination out of given domain. It call cb to several times to return each combination. It’s similar to struct GosperCombination but slightly faster in uncontrol test environment.

combination_cell

Similar to combination function except the way it return the combination. It return result through Rc<RefCell<>> to mutable slice of result. It’ll notify caller on each new result via empty callback function.

combination_sync

Similar to combination function except the way it return the combination. It return result through Rc<RefCell<>> to mutable slice of result. It’ll notify caller on each new result via empty callback function.

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.

multiply_factorial

Calculate two factorial multiply on each other. It’ll try to reduce calculation time by calculate the common value only once.

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^⚠

Similar to safe combination function except the way it return the combination. 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_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.