algorithm - 遍历给定集合的所有可能分区

Question

给定一个由向量​​表示的集合，例如[1,2,3] ，我想遍历所有可能的分区(顺序对我来说并不重要):

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

我没有在 itertools 中找到执行此操作的方法包，我也没有在其他地方找到任何东西。我见过的最接近的是 this post on StackOverflow ，但是在那篇文章中并不是所有的分区都生成了，例如[[1,3],[2]]在这种情况下。是否有一些现有的软件包可以做到这一点？或者我怎样才能做到这一点？

编辑:澄清:

• “集合”和“划分”是指数学概念，即:集合 X 是集合 A 的划分，当且仅当 X 的每个元素都是 A 的非空子集并且 A 的每个元素恰好出现在X 的一个元素。
• “用向量表示集合”是指一个向量，它以任意顺序只包含集合中的每个元素一次。特别是，它不会包含重复元素。
• 我真正想要的是一个高效的迭代器，它只产生一次(表示)每个可能的分区。 IE。我对某些方法感兴趣 create_iterator(v: Vec<T>) -> impl Iterator<Item = Vec<Vec<T>>> .我不希望生成所有分区的向量，因为这有需要更多空间的缺点，而且，使用迭代器我可以 break ，这可以大大减少运行时间。
• 示例用例可能如下所示:

for x in create_iterator(vec![1,2,3]) {
    println!("{:?}", x);
}

Answer 1

这在堆分配方面可能不是最有效的，但它确实有效!这是 playground .

fn get_partitions(input: &mut Vec<u64>) -> Vec<Vec<Vec<u64>>> {
    if input.len() == 0 {
        return Vec::new();
    }
    if input.len() == 1 {
        return vec![vec![vec![input[0]]]];
    }
    else {
        let a = input.pop().unwrap();
        let partitions = get_partitions(input);
        let mut output = Vec::new();
        for part in partitions {
            let mut tmp = part.to_vec();
            tmp.push(vec![a]);
            output.push(tmp);
            for idx in 0..part.len() {
                let mut tmp = part.to_vec();
                tmp[idx].push(a);
                output.push(tmp);
            }
        }
        return output;
    }
}

fn main() {
    let mut input = vec![1,2,3];
    let output = get_partitions(&mut input);
    println!("{:?}", output);
}

我找到了答案 here ，概述了算法。