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

}