permutations.rs

// Adapted from Python's
struct Permutations<T> {
    pool: Vec<T>,
    indices: Vec<usize>,
    cycles: Vec<usize>,
    r: usize,
    once: bool,
}

impl<T: Copy> Iterator for Permutations<T> {
    type Item = Vec<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let r = self.r;
        let n = self.pool.len();
        if self.once {
            self.once = false;
            return Some(self.indices[..r]
                .iter()
                .map(|&i| self.pool[i])
                .collect());
        }
        for i in (0..r).rev() {
            self.cycles[i] -= 1;
            if self.cycles[i] == 0 {
                self.indices[i..].rotate_left(1);
                self.cycles[i] = n - i;
            } else {
                let j = self.indices.len() - self.cycles[i];
                self.indices.swap(i, j);
                return Some(self.indices[..r]
                    .iter()
                    .map(|&i| self.pool[i])
                    .collect());
            }
        }
        None
    }
}

fn permutations<T>(it: impl Iterator<Item=T>, r: usize) -> Permutations<T> {
    let pool: Vec<_> = it.collect();
    let n = pool.len();
    Permutations {
        r,
        pool,
        cycles: ((n-r+1)..=n).rev().collect(),
        indices: (0..n).collect(),
        once: true,
    }
}

permutations_vec.rs

// https://en.wikipedia.org/wiki/Heap%27s_algorithm
fn permute_r<T: Clone>(k: usize, arr: &mut [T], out: &mut Vec<Vec<T>>) {
    if k == 0 {
        out.push(arr.to_vec());
        return;
    }
    permute_r(k - 1, arr, out);
    for i in 0..k {
        let s = i * (k % 2);
        arr.swap(s, k);
        permute_r(k - 1, arr, out);
    }
}

fn permute<T: Clone>(arr: &mut [T]) -> Vec<Vec<T>> {
    let mut out = Vec::new();
    permute_r(arr.len() - 1, arr, &mut out);
    out
}