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], [2], [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>>
{
    IteratorAdapter(|| {
        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);
    }
}

struct IteratorAdapter<G>(G);

impl<G> Iterator for IteratorAdapter<G>
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!