rust - 如何遍历切片的所有可能分区(非空子切片)？

Question

是否有惯用的解决方案来枚举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]],
]);

请注意，“subslice”而不是“subset”语义，例如，结果中不应包含 [[1, 3], [2]]。

Answer 1

通过传递闭包来处理每个分区生成时，这是一种以最少的存储量递归执行此方法的方法，该方法通过传递闭包来处理每个分区:

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

这将输出:

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

如果您确实想将所有分区累积到 Vec中，则可以这样进行:

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

这将输出

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