如何迭代 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 个 distinct 元素，就会有 24 种不同的排列）。

已经有一种方法可以使用 itertools package 生成排列（以及其他迭代器，如组合或没有替换的组合），但是对于排列，没有办法将排列限制为仅那些是独一无二的。

有一个相当有效的生成排列的算法，通常称为 Heap's Algorithm，但是这没有考虑值的相等性/重复性。

这个问题用带有生成器的语言来实现并不难，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

如果您愿意放弃使用迭代器或生成器，可以编写一个函数来输出列表的所有可能的唯一排列，代码如下。但是，由于即使在小情况下它分配的向量数量（例如两个项目的向量），实现也不是那么有效。

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

Answer 2

使用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 3

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 上有许多可用的排列板条箱。我鼓励您查看是否可以将此代码添加到其中一个或多个，以防止人们将来不得不解决这个问题。

如何迭代 Rust 中序列的所有唯一排列？

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

algorithm

rust

permutation

heaps-algorithm