Function x_permutation

pub fn x_permutation<T>(
    d: &[T],
    t: impl FnMut(&[&T]) -> bool,
    cb: impl FnMut(&[&T]),
)

A lexicographic ordered permutation based on “Algoritm X” published by Donald E. Knuth. page 20.

If order is not important, consider using heap permutation function instead. This function is 3 times slower 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::x_permutation;
 
let data = vec![1, 2, 3, 4];
let mut counter = 0;

x_permutation(&data, |_| true, |p| {
    println!("{:?}", p);
    counter += 1;
});

assert_eq!(factorial(data.len()), counter);

Skip all permutation that has 1 in first element.

use permutator::x_permutation;
 
let data : Vec<u8> = vec![1, 2, 3, 4];
let mut counter = 0;

x_permutation(&data, |f| {
    *f[0] != 1u8 // filter all permutation that start with 1
}, |p| {
    println!("{:?}", p);
    counter += 1;
});

assert_eq!(factorial(data.len()) - factorial(data.len() - 1), counter);

Multi-threads permutation example

use std::sync::{Arc, RwLock};
use permutator::{get_permutation_for, x_permutation};
 
let mut data : Vec<u8> = (0..5u8).map(|v| v).collect();
let threads = 2usize;
let chunk = data.len() / threads; // split data into 3 threads.
let complete_count = Arc::new(RwLock::new(0u64));
let total_counter = Arc::new(RwLock::new(0u64));
for i in 0..threads {
    let u_bound = match i {
        j if j == threads - 1 => data.len() as u8, // last thread do all the rest
        _ => (chunk * (i + 1)) as u8
    };
    let l_bound = (chunk * i) as u8;
    let perm = get_permutation_for(&data, data.len(), l_bound as usize).unwrap();
    let t_dat : Vec<u8> = perm.iter().map(|v| **v).collect(); // need to move to each thread
    let t_counter = Arc::clone(&complete_count); // thread completed count
    let loc_counter = Arc::clone(&total_counter); // count number of permutation
    thread::spawn(move || {
        let mut counter = 0u64;
        x_permutation(&t_dat, |v| {
            *v[0] >= l_bound && *v[0] < u_bound
        }, |_p| {
            counter += 1;
        });

        *loc_counter.write().unwrap() += counter;
        println!("Done {} in local thread", counter);
        *t_counter.write().unwrap() += 1;
    });
}

let main = thread::spawn(move || {
    let timer = Instant::now();
    loop {
        if *complete_count.read().unwrap() != (threads as u64) {
            thread::sleep(Duration::from_millis(100));
        } else {
            println!("Done {} x_permutation {} threads in {:?}", &*total_counter.read().unwrap(), threads, timer.elapsed());
            break;
        }
    }
});

main.join().unwrap();

Parameters

• d : &[T] - A data to get a permutation.
• t : FnMut(&[&T]) -> bool - A function for checking whether to traverse the branch. It shall return true if the branch need to be traversed.
• cb : FnMut(&[&T]) - A callback function that return result to caller.