如何在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的语言中实现时不太棘手，但是我觉得在Rust中（至少与上述解决方案相比，）这更棘手，因为它将需要使用迭代器（必须维护内部状态），或使用生成器（当前为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：

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