How to get every subset of a vector in Rust?

Question

What's 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're searching for is called the powerset of a vector.

Here's the code to generate the powerset of a slice of a 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 it in action here.

If you'd like a vector of references in order to prevent copies, you could 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 gist.

Answer 2

If order of elements of output is not crucial, and output like this: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] is acceptable, you can do something like this:

The underlying idea is very simple:

1. Start with an empty set: [[]]

2. Copy all your elements to a temporary variable that will be updated by adding the first element (1) to every subset -> [[1]] and add that to the original vector: [[], [1]]

3. Do step 2 for the second element (2): [[], [1], [2], [1,2]]

4. Do step 2 for the third element (3): [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

For example:

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

}