Rust Permutations

permutations.rs

use std::mem;

pub struct Permutations<T: Ord> {
    elements: Vec<T>,
    times_generated: u64
}

impl<T: Ord> Permutations<T> {
    #[inline]
    pub fn new(mut elements: Vec<T>) -> Permutations<T> {
        assert!(elements.len() <= 20, "Too many permuations: {}!", elements.len());
        elements.sort();
        Permutations {
            elements: elements,
            times_generated: 0
        }
    }

    #[inline]
    fn for_each<F>(&mut self, mut func: F) where F: FnMut(&[T]) -> () {
        while let Some(element) = self.next_borrowed() {
            func(element);
        }
    }

    #[inline]
    fn map<F, R>(&mut self, mut func: F) -> Vec<R> where F: FnMut(&[T]) -> R {
        let mut result = Vec::with_capacity(self.remaining() as usize);
        self.for_each(|permutation| result.push(func(permutation)));
        result
    }

    /// Generate the next permutation, borrowing it's contents
    #[inline] // Probably shouldn't be inlined :p
    fn next_borrowed(&mut self) -> Option<&[T]> {
        if self.times_generated == 0 {
            self.times_generated += 1;
            return Some(&mut self.elements);
        }
        {
        let ref mut elements = self.elements;
        let size = elements.len();
        // Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation
        let mut k = size - 2;
        while elements[k] >= elements[k + 1] {
            if k == 0 {
                debug_assert!(self.times_generated == factorial(elements.len()));
                return None;
            } else {
                k -= 1;
            }
        }
        // Find the largest index l greater than k such that a[k] < a[l]
        let mut l = k + 1;
        while l + 1 < size && elements[k] < elements[l + 1] {
            l += 1;
        }
        // Swap the value of a[k] with that of a[l]
        elements.swap(k, l);
        // Reverse the sequence from a[k + 1] up to and including the final element a[n]
        (&mut elements[k + 1..]).reverse();
        debug_assert!(self.times_generated < factorial(size));
        self.times_generated += 1;
        }
        Some(&mut self.elements)
    }

    #[inline]
    fn remaining(&self) -> u64 {
        factorial(self.elements.len()) - self.times_generated
    }
}

impl<T: Clone + Ord> Iterator for Permutations<T> {
    type Item = Vec<T>;

    #[inline]
    fn next(&mut self) -> Option<Vec<T>> {
        self.next_borrowed().map(Vec::from)
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.remaining();
        (remaining as usize, Some(remaining as usize))
    }
}

#[inline]
pub fn factorial(num: usize) -> u64 {
    assert!(num <= 20, "Factorial overflow: {}!", num);
    FACTORIALS[num]
}
static FACTORIALS: [u64; 21] = [
    1,
    1,
    1 * 2,
    1 * 2 * 3,
    1 * 2 * 3 * 4,
    1 * 2 * 3 * 4 * 5,
    1 * 2 * 3 * 4 * 5 * 6,
    1 * 2 * 3 * 4 * 5 * 6 * 7,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8,    
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20
];