How to iterate over all unique permutations of a sequence in Rust?

Question

Given a list of values, such as vec![0, 0, 1, 2], I would like to create an iterator that generates all of its unique permutations. That is,

[0, 0, 1, 2]
[0, 0, 2, 1]
[0, 1, 0, 2]
[0, 1, 2, 0]
[0, 2, 0, 1]
[0, 2, 1, 0]
[1, 0, 0, 2]
[1, 0, 2, 0]
[1, 2, 0, 0]
[2, 0, 0, 1]
[2, 0, 1, 0]
[2, 1, 0, 0]

(Note that there are 12 different permutations, while if we had 4 distinct elements, there would be 24 different permutations).

There is already a way to generate permutations (as well as other iterators like combinations or combinations without replacements) using the itertools package, but for permutations, there is no way to limit the permutations to only those that are unique.

There is a fairly efficient algorithm for generating permutations in general known as Heap's Algorithm, however this does not take into account the equality / duplicity of values.

This problem is not too tricky to implement in languages with generators, such as Python, but I feel like this is more tricky in Rust (at least compared to the solution above), since it would require using iterators (which must maintain internal state), or using generators (which are currently unstable).

Answer 1

The Python solution can be converted into an iterator:

use std::collections::btree_set::{BTreeSet, IntoIter};

enum UniquePermutations {
    Leaf {
        elements: Option<Vec<i32>>,
    },
    Stem {
        elements: Vec<i32>,
        unique_elements: IntoIter<i32>,
        first_element: i32,
        inner: Box<Self>,
    },
}

impl UniquePermutations {
    fn new(elements: Vec<i32>) -> Self {
        if elements.len() == 1 {
            let elements = Some(elements);
            Self::Leaf { elements }
        } else {
            let mut unique_elements = elements
                .clone()
                .into_iter()
                .collect::<BTreeSet<_>>()
                .into_iter();

            let (first_element, inner) = Self::next_level(&mut unique_elements, elements.clone())
                .expect("Must have at least one item");

            Self::Stem {
                elements,
                unique_elements,
                first_element,
                inner,
            }
        }
    }

    fn next_level(
        mut unique_elements: impl Iterator<Item = i32>,
        elements: Vec<i32>,
    ) -> Option<(i32, Box<Self>)> {
        let first_element = unique_elements.next()?;

        let mut remaining_elements = elements;

        if let Some(idx) = remaining_elements.iter().position(|&i| i == first_element) {
            remaining_elements.remove(idx);
        }

        let inner = Box::new(Self::new(remaining_elements));

        Some((first_element, inner))
    }
}

impl Iterator for UniquePermutations {
    type Item = Vec<i32>;

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            Self::Leaf { elements } => elements.take(),
            Self::Stem {
                elements,
                unique_elements,
                first_element,
                inner,
            } => loop {
                match inner.next() {
                    Some(mut v) => {
                        v.insert(0, *first_element);
                        return Some(v);
                    }
                    None => {
                        let (next_fe, next_i) =
                            Self::next_level(&mut *unique_elements, elements.clone())?;
                        *first_element = next_fe;
                        *inner = next_i;
                    }
                }
            },
        }
    }
}

fn main() {
    let items = vec![0, 0, 1, 2];
    for perm in UniquePermutations::new(items) {
        println!("{:?}", perm);
    }
}

The generator solution hides a lot of allocation and complexity which is brought to the forefront here. The call stack becomes the linked list of inner fields and we have to do a fair amount of cloning.

I didn't perform any micro optimizations, such as either using a VecDeque to insert at the head of the list, or adding a wrapper iterator adapter that reverses the Vec before finally returning it to the caller. I also used a BTreeSet to focus on ensuring that the set was unique; feel free to change it to your pure Vec based solution.

I've also not done any profiling or benchmarking. This may or may not be any faster.

There are a number of permutation crates available on crates.io. I encourage you to see if this code can be added to one or more of them to prevent people from having to figure this out in the future.

Answer 2

If you are willing to give up on using iterators or generators, it's possible to write a function that outputs all possible unique permutations of a list, with the code below. The implementation isn't that efficient though, due to the number of vectors it allocates even in small cases (e.g. a vector of two items).

fn unique_permutations<T: Clone>(items: Vec<T>) -> Vec<Vec<T>>
where
    T: Ord,
{
    if items.len() == 1 {
        vec![items]
    } else {
        let mut output: Vec<Vec<T>> = vec![];

        // Obtain a list of the unique elements.
        // Sorting and deduping should be faster than using a hashset for most small n.
        let mut unique_items = items.clone();
        unique_items.sort();
        unique_items.dedup();
        for first in unique_items {
            let mut remaining_elements = items.clone();

            // this feature is unstable
            // remaining_elements.remove_item(first);

            let index = remaining_elements.iter().position(|x| *x == first).unwrap();
            remaining_elements.remove(index);

            for mut permutation in unique_permutations(remaining_elements) {
                permutation.insert(0, first.clone());
                output.push(permutation);
            }
        }
        output
    }
}