Power set of a Vec


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.


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() {

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]> {
        (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]> {
            .map(move |(start, end)| &a[start..end])

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

fn main() {
    for t in power_set(0..).take(8) {

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)
      p = [[]]
      yield []
      for x in a
         b = p.map(|s| s+[x])
         for t in b do yield t end

for t in power_set(0..).take(8)

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

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.