Как перебрать все уникальные перестановки последовательности в Rust?

Question

Учитывая список значений, например vec![0, 0, 1, 2], я хотел бы создать итератор, генерирующий все его уникальные перестановки. То есть

[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]

(обратите внимание, что существует 12 различных перестановок, в то время как если бы у нас было 4 различных элементов, было бы 24 различных перестановки).

Там Это уже способ генерировать перестановки (а также другие итераторы, такие как комбинации или комбинации без замен) с использованием пакета itertools , но для перестановок нет способа ограничить перестановки только теми, которые являются уникальными.

Существует довольно эффективный алгоритм генерации перестановок, в общем известный как Алгоритм кучи , однако он не учитывает равенство / двойственность значений.

Эта проблема не слишком сложно реализовать в языках с генераторами, , таких как Python, но я чувствую, что это более сложно в Rust (по крайней мере, по сравнению с решением выше), так как для этого потребуется использование итераторов ( который должен поддерживать внутреннее состояние), или используя генераторы (которые в настоящее время нестабильны ).

Answer 1

Используйте больше инструментов из itertools, а именно: 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);
    }
}

См. Также:

• Как добавить новые методы итератору?

Answer 2

Решение Python можно преобразовать в итератор:

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

Генераторное решение скрывает большое количество ресурсов и сложностей, которые здесь выдвигаются на первый план. Стек вызовов становится связанным списком полей inner, и мы должны сделать немало клонирования.

Я не выполнял микрооптимизации, например, с использованием VecDeque для вставки в заголовок списка или добавление адаптера-итератора обертки, который обращает Vec перед тем, как окончательно вернуть его вызывающей стороне. Я также использовал BTreeSet, чтобы сосредоточиться на том, чтобы набор был уникальным; не стесняйтесь сменить его на свое чистое решение на основе Vec.

Я также не проводил профилирование или сравнительный анализ. Это может быть или не быть быстрее.

На сайте crates.io доступно несколько ящиков с перестановками. Я призываю вас посмотреть, можно ли добавить этот код к одному или нескольким из них, чтобы люди не могли понять это в будущем.

Answer 3

Если вы готовы отказаться от использования итераторов или генераторов, можно написать функцию, которая выводит все возможные уникальные перестановки списка с помощью приведенного ниже кода. Однако реализация не столь эффективна из-за количества векторов, которые она выделяет даже в небольших случаях (например, вектор из двух элементов).

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