 # Power set of a Vec

Hello,

Let’s say that I have a vector

`let x = vec![0, 1, 2];`

and I want to iterate over all the subvectors. That is, I want to iterate over

``````[], , , , [0, 1], [0, 2], [1, 2], [0, 1, 2]
``````

I have some idea on how to implement this, but I’m not sure they are really idiomatic.

Do you have any suggestion?

Thank you!

You could `flat_map` increasing lengths of `Itertools::combinations`.

2 Likes

Actually, tuple combinations of slice indexes might work better, something like:

``````let x: Vec<_> = ...;

let iter = (0..=x.len()).tuple_combinations().map(|(start, end)| &x[start..end]);
``````

I’ve implemented the first solution. Work pretty fine. I will take a look at the second option. Thanks!

``````fn power_set<T: Clone>(a: &Vec<T>) -> Vec<Vec<T>> {
a.iter().fold(vec![vec![]], |mut p, x| {
let i = p.clone().into_iter()
.map(|mut s| {s.push(x.clone()); s});
p.extend(i); p})
}

fn main() {
println!("{:?}",power_set(&vec![0,1,2]));
}
``````

minor nit: Never use `&Vec<T>` it has no benefits over `&[T]` and prevents other types that can be coerced to a slice from being used.

``````fn power_set<T: Clone>(a: &[T]) -> Vec<Vec<T>> { ... }
``````

Then by further nitpicking,

``````fn power_set<T: Clone>(a: impl Iterator<Item=T>) -> Vec<Vec<T>>
``````

Well, if were going there it should be `IntoIterator` to seemlessly allow most collections. But I think changing to a slice is enough for many uses cases.

With slices, we don’t need any allocation:

``````fn power_set<'a, T>(a: &[T]) -> impl Iterator<Item = &[T]> {
std::iter::once([].as_ref()).chain(
(0..a.len()).flat_map(move |start| {
(start + 1..=a.len())
.map(move |end| &a[start..end])
})
)
}
``````

Or with `itertools`:

``````fn power_set<'a, T>(a: &[T]) -> impl Iterator<Item = &[T]> {
std::iter::once([].as_ref()).chain(
(0..=a.len())
.tuple_combinations()
.map(move |(start, end)| &a[start..end])
)
}
``````
1 Like

This doesn’t produce `[0, 2]` when you feed it the input `&[0, 1, 2]`

1 Like

Oh, right – I got all subslices, but you can’t get all combinations this way.

A lazy variant:

``````#![feature(generators, generator_trait)]

fn power_set<T: Clone>(a: impl IntoIterator<Item=T>)
-> impl Iterator<Item=Vec<T>>
{
let mut p = vec![vec![]];
yield vec![];
for x in a.into_iter() {
let b: Vec<_> = p.clone().into_iter()
.map(|mut s| {s.push(x.clone()); s}).collect();
for t in b.clone() {yield t;}
p.extend(b);
}
}).into_iter()
}

fn main() {
for t in power_set(0..).take(8) {
println!("{:?}",t);
}
}

where G: std::ops::Generator<Return=()> + Unpin
{
type Item = G::Yield;
fn next(&mut self) -> Option<Self::Item> {
match std::pin::Pin::new(&mut self.0).resume() {
std::ops::GeneratorState::Yielded(item) => Some(item),
std::ops::GeneratorState::Complete(_) => None,
}
}
}
``````
1 Like

The same in Moss:

``````function power_set(a)
fn*||
p = [[]]
yield []
for x in a
b = p.map(|s| s+[x])
for t in b do yield t end
p.push(*b)
end
end
end

for t in power_set(0..).take(8)
print(t)
end
``````

Thank you all for the answers. I wasn’t expecting that much!