Heap's Permutation Algorithm in Rust

heaps_algorithm.rs

// Author: Lohann Paterno Coutinho Ferreira
//
// Heap's Permutation Algorithm

/// Move all duplicated elements to the end of the array.
/// Returns the number of distinct elements.
fn move_duplicated<T: PartialEq>(array: &mut [T]) -> usize {
    let mut n = array.len();
    let mut i = 0;
    while i < n {
        let mut j = i + 1;
        while j < n {
            if <T as PartialEq>::eq(&array[i], &array[j]) {
                n -= 1;
                array.swap(j, n);
            } else {
                j += 1;
            }
        }
        i += 1;
    }
    n
}

/// Non-Recursive Heap's Permutation
pub fn heap_permutation<const N: usize, T, R, F>(array: &mut [T; N], mut callback: F) -> Option<R>
where
    T: Eq,
    R: Send,
    F: FnMut(&[T; N]) -> Option<R>,
{
    // c[k] encodes the for-loop counter for
    // when  permutations(k + 1, A) is called
    let mut c: [usize; N] = [0usize; N];

    // (optional) remove duplicated elements.
    let len = move_duplicated(array);
    if let Some(result) = callback(array) {
        return Some(result);
    }

    // i acts similarly to a stack pointer
    let mut i = 1;
    while i < len {
        if c[i] < i {
            let j = if (i % 2) == 0 { 0 } else { c[i] };
            array.swap(j, i);
            if let Some(result) = callback(array) {
                return Some(result);
            }

            // Swap has occurred ending the while-loop.
            // Simulate the increment of the while-loop counter
            c[i] += 1;

            // Simulate recursive call reaching the base case by bringing
            // the pointer to the base case analog in the array
            i = 1;
        } else {
            // Calling permutations(i+1, A) has ended as the while-loop
            // terminated. Reset the state and simulate popping the stack
            // by incrementing the pointer.
            c[i] = 0;
            i += 1;
        }
    }
    None
}

fn internal_recursive_permutation<T, R, F>(array: &mut [T], n: usize, callback: &mut F) -> Option<R>
where
    T: Eq,
    R: Send,
    F: FnMut(&[T]) -> Option<R>,
{
    if n <= 1 {
        return (*callback)(array);
    }

    for i in 0..n {
        if let Some(result) = internal_recursive_permutation(array, n - 1, callback) {
            return Some(result);
        }
        if (n % 2) == 1 {
            array.swap(0, n - 1);
        } else {
            array.swap(i, n - 1);
        }
    }
    None
}

pub fn recursive_permutation<T, R, F>(array: &mut [T], mut callback: F) -> Option<R>
where
    T: Eq,
    R: Send,
    F: FnMut(&[T]) -> Option<R>,
{
    let len = remove_duplicated(array);
    internal_recursive_permutation::<T, R, F>(array, len, &mut callback)
}

fn main() {
    // NON-RECURSIVE
    let mut counter = 0;
    heap_permutation(&mut [1, 2, 3, 4], |array| {
        counter += 1;
        println!("({counter}) {array:?}");
        Option::<()>::None
    });
    println!();
    
    // WITH DUPLICATED ELEMENTS
    counter = 0;
    heap_permutation(&mut [1, 2, 2, 3], |array| {
        counter += 1;
        println!("({counter}) {array:?}");
        Option::<()>::None
    });
    println!();
    
    // RECURSIVE
    counter = 0;
    recursive_permutation(&mut [1, 2, 2, 3], |array| {
        counter += 1;
        println!("({counter}) {array:?}");
        Option::<()>::None
    });
}