Create all permutations from a collection

permutations.rs

#![feature(test)]
/// My naive implementation based on
/// [this javascript implementation](https://gist.github.com/thebopshoobop/b9531ceb67faae0a48a9f4aadb1aed55#file-perms_recursive-js)
/// ([blog post here](https://medium.com/@rwillt/two-very-different-algorithms-for-generating-permutations-412e8cc0039c))
///
/// NB: Runs fine on stable rust, unstable only needed for the benchmarking
///
/// For comparison:
///
/// using [itertools](https://crates.io/crates/itertools):
/// test tests::test_itertools ... bench:   3,108,820 ns/iter (+/- 41,462)
///
/// using python's iterools:
/// ```console
/// $ python3 -m timeit -s 'from itertools import permutations; l=list(range(8))' 'list(permutations(l))'
/// 200 loops, best of 5: 1.82 msec per loop
/// ```

pub fn permutations1<T: Clone>(v: &[T]) -> Vec<Vec<T>> {
    let mut perms = Vec::new();
    match v.len() {
        0..=1 => return vec![v.to_vec()],
        _ => {
            for idx in 0..(v.len()) {
                let current = v.get(idx).unwrap();
                let rest = [&v[..idx], &v[idx + 1..]].concat();
                let ps = permutations1(&rest);
                for mut p in ps {
                    let mut new = vec![current.clone()];
                    new.extend(p.drain(..));
                    perms.push(new);
                }
            }
        }
    }
    perms
}

/// Version using heaps algorithm
/// I don't recall where I found the heaps implementation. Maybe here?
/// https://users.rust-lang.org/t/heaps-algorithm-incomplete/32585
pub fn permutations2<T: Clone>(v: &mut [T]) -> Vec<Vec<T>> {
    fn heaps_alg<T>(v: &mut [T], n: usize) -> Vec<Vec<T>>
    where
        T: Clone,
    {
        if n == 1 {
            return vec![v.to_vec()];
        }

        let mut perms = Vec::new();
        for x in 0..n - 1 {
            perms.extend(heaps_alg(v, n - 1));
            if n % 2 == 0 {
                v.swap(n - 1, x);
            } else {
                v.swap(n - 1, 0);
            }
        }
        perms.extend(heaps_alg(v, n - 1));
        perms
    }
    let len = v.len();
    heaps_alg(v, len)
}

#[cfg(test)]
mod tests {
    use super::*;
    extern crate test;
    use test::Bencher;
    #[test]
    fn test_perms1() {
        let mut perms = permutations1(&[1, 2, 3]);
        perms.sort();
        let answer = [
            [1, 2, 3],
            [1, 3, 2],
            [2, 1, 3],
            [2, 3, 1],
            [3, 1, 2],
            [3, 2, 1],
        ];
        assert_eq!(perms, answer)
    }

    #[test]
    fn test_perms2() {
        let mut perms = permutations2(&mut [1, 2, 3]);
        perms.sort();
        let answer = [
            [1, 2, 3],
            [1, 3, 2],
            [2, 1, 3],
            [2, 3, 1],
            [3, 1, 2],
            [3, 2, 1],
        ];
        assert_eq!(perms, answer)
    }

    #[bench]
    /// test tests::bench_perms1 ... bench:  31,964,050 ns/iter (+/- 702,237)
    fn bench_perms1(b: &mut Bencher) {
        let input: Vec<_> = (0_u32..8).collect();
        b.iter(|| permutations1(&input))
    }

    #[bench]
    /// test tests::bench_perms2 ... bench:   6,672,604 ns/iter (+/- 194,492)
    fn bench_perms2(b: &mut Bencher) {
        let mut input: Vec<_> = (0_u32..8).collect();
        b.iter(|| permutations2(&mut input))
    }
}