如何在Rust中获取一个向量的所有子集？

Question

在Rust中获取向量的每个子集的最简单/最惯用方法是什么？

let v = vec![1,2,3];
assert_eq!(subsets(v), [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]);

- timlyo

Answer 1

你正在寻找的是向量的powerset。

以下是生成向量切片的幂集的代码。

fn powerset<T>(s: &[T]) -> Vec<Vec<T>> where T: Clone {
    (0..2usize.pow(s.len() as u32)).map(|i| {
         s.iter().enumerate().filter(|&(t, _)| (i >> t) % 2 == 1)
                             .map(|(_, element)| element.clone())
                             .collect()
     }).collect()
}   

fn main() {
    let v = vec![1,2,3];
    println!("{:?}", v);
    let pset = powerset(&v);
    println!("{:?}", pset);
}

请在此处查看其实际应用。

如果您想获取参考向量以防止复制，可以进行简单的更改：

fn powerset<T>(s: &[T]) -> Vec<Vec<&T>> {
    (0..2usize.pow(s.len() as u32)).map(|i| {
         s.iter().enumerate().filter(|&(t, _)| (i >> t) % 2 == 1)
                             .map(|(_, element)| element)
                             .collect()
     }).collect()
} 

请点击此处查看要点。

- erip

---

我认为你可以通过返回Vec<Vec<&T>>来避免Clone的限制。 - Matthieu M.

@MatthieuM。确实！发现得好，谢谢你的提示。 :) - erip

Answer 2

如果输出元素的顺序不重要，并且像这样的输出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 是可以接受的，那么您可以像这样做：

其基本思想非常简单：

1. 从一个空集开始：[[]]

2. 将所有元素复制到一个临时变量中，该变量将通过将第一个元素（1）添加到每个子集来更新 -> [[1]] 并将其添加到原始向量中：[[], [1]]

3. 对第二个元素（2）执行步骤 2：[[], [1], [2], [1,2]]

4. 对第三个元素（3）执行步骤 2：[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

例如：

fn powerset(s: &[i32]) -> Vec<Vec<i32>> {
    let mut subsets: Vec<Vec<i32>> = vec![];
    let empty: Vec<i32> = vec![];
    subsets.push(empty);

    let mut updated: Vec<Vec<i32>> = vec![]; 

    for ele in s {
        for mut sub in subsets.clone() {
            sub.push(*ele);
            updated.push(sub);
        }
        subsets.append(&mut updated);
    }
    subsets
}

fn main() {
    let my_vec: Vec<i32> = vec![1,2,3];

    let subs = powerset(&my_vec);
    println!("{:?}", subs);

}

- Akavall

Answer 3

这里是一种更加实用的解决方案，它使用了 itertools crate。

我对 Rust 还不熟悉，所以关于克隆/借用/所有权等方面的决策可能不是最好的，但希望实现的要点能够有所帮助。

use itertools::Itertools;

fn subsets<T: Clone>(items: Vec<T>) -> Vec<Vec<T>> {
    (0..=items.len())
        .map(|count| items.clone().into_iter().combinations(count))
        .flatten()
        .collect()
}

fn main() {
    // for example ...
    let it = subsets(vec![12, 24, 36]);
    println!("{:?}", it);
}

- achalk

---

更符合惯用语的 Rust 会在子集中删除返回状态，使其变得隐式。虽然看起来非常不错。我喜欢其中使用 combinations 的方式，它使实际逻辑保持简单。 - timlyo

@timlyo 谢谢，你说的“在子集中删除return状态”是什么意思？ - achalk

抱歉，打错了。我是指删除 return 语句。如果您删除 return 和分号，则会将其转换为隐式返回，因此它将如下所示 https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=280506eaca8ad2a4f21b768e803b2592 - timlyo