0

Is there an idiomatic solution to enumerate all possible non-empty subdivisions of a vector/slice in Rust?

let v = vec![1, 2, 3];

let subdivisions: Vec<_> = iterate_all_subdivisions(&v).collect();

assert_eq!(subdivisions, vec![
  vec![vec![1], vec![2], vec![3]],
  vec![vec![1, 2], vec![3]],
  vec![vec![1], vec![2, 3]],
  vec![vec![1, 2, 3]],
]);

Note the "subslice" instead of "subset" semantics, e.g., [[1, 3], [2]] should not be in the result.

bluenote10
  • 23,414
  • 14
  • 122
  • 178
  • There is a related question on [computing the powerset](https://stackoverflow.com/q/40718975/1804173), but I'm not sure if the best strategy is to use this as a base. [`itertools::partition`](https://docs.rs/itertools/0.9.0/itertools/fn.partition.html) also seems to serve a different purpose. – bluenote10 Jun 20 '20 at 13:07
  • 1
    I found very inefficient recursive solution with a lot of Vec allocations. Maybe it could be of some help. https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=10b6409c294a21f364548fa5217c304e – tsionyx Jun 20 '20 at 16:14

1 Answers1

1

Here's a way to do it recursively with minimal storage, and without needing to make copies, by passing a closure to handle each partition as it is generated:

fn iterate_all_subdivisions<'a, T, F>(head: &mut Vec<&'a [T]>, rest: &'a [T], f: &mut F)
where
    F: FnMut(&[&[T]]),
{
    if rest.len() == 0 {
        f(head);
    } else {
        for i in 1..=rest.len() {
            let (next, tail) = rest.split_at(i);
            head.push(next);
            iterate_all_subdivisions(head, tail, f);
            head.pop();
        }
    }
}

fn main() {
    let v: Vec<i32> = vec![1, 2, 3];
    iterate_all_subdivisions(&mut Vec::new(), &v, &mut |x| println!("{:?}", x));
}

This will output:

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

If you do want to accumulate all the partitions into a Vec, you could do it like this:

fn main() {
    let v: Vec<i32> = vec![1, 2, 3];
    let mut results: Vec<Vec<Vec<i32>>> = Vec::new();
    iterate_all_subdivisions(&mut Vec::new(), &v, &mut |x| {
        results.push(x.iter().map(|y| y.to_vec()).collect());
    });
    println!("{:?}", results);
}

This will output

[[[1], [2], [3]], [[1], [2, 3]], [[1, 2], [3]], [[1, 2, 3]]]
Brent Kerby
  • 1,397
  • 8
  • 14