如何在 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);
    }
}

也可以看看：

• 如何向迭代器添加新方法？