CODEWITHSUNDEEP
rust
timlyo
timlyo

Reputation: 2404

How to get every subset of a vector in Rust?

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

Upvotes: 11

Views: 4302

Answers (3)

achalk
achalk

Reputation: 3459

Here is a more functional flavoured solution that uses the itertools crate.

I am new to Rust so FYI my decisions around cloning/borrowing/ownership/etc may not be the best, but hopefully the gist of the implementation is helpful.

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

Upvotes: 2

Akavall
Akavall

Reputation: 86356

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

}

Upvotes: 2

erip
erip

Reputation: 16995

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.

Upvotes: 16

Related Questions