Generate permutations of any N items, where N is a const generic uint.

const_combinatorics.rs

use array_init::array_init;

fn permutations<T: Copy, const N: usize>(items: &[T; N]) -> Vec<[T; N]> {
    permute_naturals::<N>(1, vec![[0; N]])
        .into_iter()
        .map(|perm| array_init(|i| items[perm[i]]))
        .collect()
}

/// Generate all `n!` permutations of the natural numbers 0..n
fn permute_naturals<const N: usize>(i: usize, partials: Vec<[usize; N]>) -> Vec<[usize; N]> {
    if i == N {
        return partials;
    }
    let next_partials = partials
        .iter()
        .flat_map(|curr| (0..=i).map(move |j| insert_into(curr.clone(), i, j)))
        .collect();
    permute_naturals(i + 1, next_partials)
}

/// Insert the given value into the array at the given index.
/// Elements past the index will be moved one index to the right.
fn insert_into<const N: usize>(curr: [usize; N], val: usize, index: usize) -> [usize; N] {
    let mut permutation = [0; N];
    for i in 0..index {
        permutation[i] = curr[i];
    }
    permutation[index] = val;
    for i in index + 1..curr.len() {
        permutation[i] = curr[i - 1];
    }
    permutation
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashSet;

    #[test]
    fn test_insert_into() {
        let expected = [1, 2, 3];
        let actual = insert_into([1, 3, 0], 2, 1);
        assert_eq!(actual, expected);
    }

    #[test]
    fn test_permute_naturals() {
        for permutation in permute_naturals::<3>(0, vec![[0; 3]]) {
            let num_distinct_elements = HashSet::from(permutation.clone()).len();
            assert_eq!(num_distinct_elements, permutation.len())
        }
    }

    #[test]
    fn test_permutations() {
        let perms = permutations(&["a", "b", "c"]);
        assert_eq!(perms.len(), 6, "{:?}", perms);
        assert_eq!(perms.into_iter().collect::<HashSet<_>>().len(), 6);
    }

    #[test]
    fn test_permutations_base_case() {
        let perms = permutations(&["a"]);
        assert_eq!(perms, vec![["a"]]);
    }
}