advent_of_code/common/
permutation.rs

1/// Generate all permutations of a sequence using Heap's algorithm.
2pub fn all_permutations<F, T>(sequence: &mut [T], on_permutation: &mut F) -> Result<(), String>
3where
4    F: FnMut(&[T]) -> Result<(), String>,
5{
6    let size = sequence.len();
7    all_permutations_internal(sequence, size, on_permutation)
8}
9
10fn all_permutations_internal<F, T>(
11    sequence: &mut [T],
12    size: usize,
13    on_permutation: &mut F,
14) -> Result<(), String>
15where
16    F: FnMut(&[T]) -> Result<(), String>,
17{
18    if size <= 1 {
19        return on_permutation(sequence);
20    }
21
22    for i in 0..size {
23        all_permutations_internal(sequence, size - 1, on_permutation)?;
24
25        if size % 2 == 1 {
26            // If size is odd, swap first and last element.
27            sequence.swap(0, size - 1);
28        } else {
29            // If size is even, swap ith and last element.
30            sequence.swap(i, size - 1);
31        }
32    }
33
34    Ok(())
35}