Function permutator::k_permutation

source · [−]
pub fn k_permutation<'a, T, F>(d: &'a [T], k: usize, cb: F) where
    T: 'a,
    for<'r> F: FnMut(&'r [&'a T]) + 'a, 
Expand description

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]

The implementation calculate each combination by large_combination function then apply Heap’s algorithm. There’s KPermutationIterator struct that also generate KPermutationIterator but in iterative style. The performance of this function is slightly faster than KPermutationIterator struct by about 15%-20% tested in uncontrol environment.

Examples

The example below will generate 4-permutation over 6 data items. The first combination will be used to generate all permutation first. So the first three result will be [1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4] as per Heap permutation algorithm. After all permutation for [1, 2, 3, 4] is calculated, it’ll use Gospel algorithm to find next combination which is [1, 2, 3, 5] then permutate it until every permutation is done. It’ll keep repeating above process until last combination, which is [3, 4, 5, 6], is completely permuted then the function will return.

   use permutator::k_permutation;
   use std::time::{Instant};
 
   let data = [1, 2, 3, 4, 5, 6];
   let mut counter = 0;
   let timer = Instant::now();
 
   k_permutation(&data, 4, |permuted| {
       // uncomment line below to print all k-permutation
       // println!("{}:{:?}", counter, permuted);
       counter += 1;
   });
   println!("Done {} permuted in {:?}", counter, timer.elapsed());

Panic

This function panic when k == 0 or k > d.len()

Notes

  1. This function doesn’t support jumping into specific nth permutation because the permutation is out of lexicographic order per Heap’s algorithm limitation. For jumping into specific position, it require lexicographic ordered permutation.
  2. This function take callback function to speed up permutation processing. It will call the callback right in the middle of Heap’s loop then continue the loop.
  3. This function use single thread.

See