1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/// Generate all permutations of a sequence using Heap's algorithm.
pub fn all_permutations<F, T>(sequence: &mut [T], on_permutation: &mut F) -> Result<(), String>
where
    F: FnMut(&[T]) -> Result<(), String>,
{
    let size = sequence.len();
    all_permutations_internal(sequence, size, on_permutation)
}

fn all_permutations_internal<F, T>(
    sequence: &mut [T],
    size: usize,
    on_permutation: &mut F,
) -> Result<(), String>
where
    F: FnMut(&[T]) -> Result<(), String>,
{
    if size == 1 {
        return on_permutation(sequence);
    }

    for i in 0..size {
        all_permutations_internal(sequence, size - 1, on_permutation)?;

        if size % 2 == 1 {
            // If size is odd, swap first and last element.
            sequence.swap(0, size - 1);
        } else {
            // If size is even, swap ith and last element.
            sequence.swap(i, size - 1);
        }
    }

    Ok(())
}