Struct permutator::GosperCombinationRefIter

pub struct GosperCombinationRefIter<'a, T> where
    T: 'a,  { /* private fields */ }

Deprecated

This iterator family is now deprecated. Consider using LargeCombinationCellIter instead. This is because current implementation need to copy every ref on every iteration which is inefficient. On uncontroll test environment, this iterator take 2.29s to iterate over 30,045,015 combinations. The LargeCombinationCellIter took only 345.44ms.

Create an unsafe combination iterator that return result to mutable pointer. It use Gosper’s algorithm to pick a combination out of given data. The produced combination provide no lexicographic order.

The returned combination will be a reference into given data. Each combination return from iterator by storing into given *mut [&T] along with empty Option.

Unsafe

This object took raw mutable pointer and convert in upon object instantiation via new function thus all unsafe Rust conditions will be applied on all method.

Rationale

It uses unsafe to take a mutable pointer to store the result to avoid the cost of using Rc<RefCell<>>. In uncontroll test environment, this struct perform a complete iteration over 657,800 combinations in about 47ms where GosperCombinationCellIter took about 52ms. This function is very much alike unsafe_combination function but took Iterator approach.

Examples

Given slice of [1, 2, 3, 4, 5]. It will produce following combinations: [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5] Here’s an example of code printing above combination.

   use permutator::{GosperCombinationRefIter};
   use std::time::{Instant};
   let data = &[1, 2, 3, 4, 5];
   let mut result : &mut[&i32] = &mut [&data[0]; 3];
   unsafe {
        let mut gosper = GosperCombinationRefIter::new(&[1, 2, 3, 4, 5], 3, result as *mut [&i32]);
        let mut counter = 0;
        let timer = Instant::now();

        for _ in gosper {
            println!("{}:{:?}", counter, result);
            counter += 1;
        }

        println!("Total {} combinations in {:?}", counter, timer.elapsed());
   }

Limitation

Gosper algorithm need to know the MSB (most significant bit). The current largest known MSB data type is u128. This make the implementation support up to 128 elements slice.

See

• Gospel’s algorithm in Wikipedia page, October 9, 2018

Implementations

impl<'a, T> GosperCombinationRefIter<'a, T>

pub unsafe fn new(
    data: &'a [T],
    r: usize,
    result: *mut [&'a T]
) -> GosperCombinationRefIter<'a, T>

Create new combination generator using Gosper’s algorithm. r shall be smaller than data.len().

Note: It perform no check on given parameter. If r is larger than length of data then iterate over it will not occur. The iteration will be end upon enter.

pub fn len(&self) -> usize

Total number of combinations this iterate can return. It will equals to n!/((n-r)!*r!)

Trait Implementations

impl<'a, T> IntoIterator for GosperCombinationRefIter<'a, T>

type Item = ()

The type of the elements being iterated over.

type IntoIter = CombinationRefIter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> CombinationRefIter<'a, T>

Creates an iterator from a value.