如何获取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]]); 

Answer 1

你在搜索什么叫做powerset的一个向量。

下面是生成矢量切片的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); 
} 

看到它在行动here。

如果您想引用的一个载体，以防止拷贝，你可以做一个简单的变化：

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

见here大意。

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. 执行步骤2的第三元件（3）：[[], [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); 

}