algorithm - 如何在 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 package 生成排列(以及其他迭代器，如组合或没有替换的组合)。 ，但对于排列，没有办法将排列限制为唯一的排列。
有一种相当有效的算法来生成排列，通常称为 Heap's Algorithm ，但是这并没有考虑到值(value)的平等/双重性。
在带有生成器的语言中实现这个问题并不太棘手， such as Python ，但我觉得这在 Rust 中更棘手(至少与上面的解决方案相比)，因为它需要使用迭代器(必须保持内部状态)或使用生成器(当前是 unstable )。

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

也可以看看:

How can I add new methods to Iterator?