How to get every subset of a vector in Rust?
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.
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:
Start with an empty set:
[[]]
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]]
Do step 2 for the second element (
2
):[[], [1], [2], [1,2]]
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);
}