How to get every subset of a vector in Rust?

Question

What is the easiest / most idiomatic way to get every subset of a vector in 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

What you are looking for is called the powerset of the vector.

Here is the code to generate the slice syntax of the vector.

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

See in action here .

If you want to use the link vector to prevent copying, you can make a simple change:

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

See here for the gist.

Answer 2

If the order of the output elements is not critical and is output as follows: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]valid, you can do something like this:

:

• : [[]]

• , ​​ (1) → [[1]] : [[], [1]]

• (2): [[], [1], [2], [1,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);

}