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).

Ambulacrum

Is your input list of values always sorted? – Satirical

No, in this case the order of the elements in the input list is arbitrary (since both will have the same set of permutations). – Ambulacrum

Answer 1

Use more tools from itertools, namely Itertools::unique:

use itertools::Itertools; // 0.8.2

fn main() {
    let items = vec![0, 0, 1, 2];
    for perm in items.iter().permutations(items.len()).unique() {
        println!("{:?}", perm);
    }
}

See also:

• How can I add new methods to Iterator?

Irrecoverable

I didn't notice this iterator method before, so knowing this is available is great - thanks for sharing. :-) That said, the runtime of this solution can be very poor (compared to the solution I posted) in some scenarios. Ex. the vector only has a few (1-3) distinct items, like [1, 0, 0, 0, 0, 0, 0, 0]; then this code will try calculating all 8! nondistinct permutations (then filtering by uniqueness) versus calculating the 8 possible distinct permutations up front (if I'm not mistaken). – Ambulacrum

Answer 2

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.

Irrecoverable

Answer 3

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
    }
}

Ambulacrum