java - 获取集合的所有可能分区

Question

在 Java 中，我有一个集合，我想在其中获取所有可能的子集组合，它们的并集构成主集。 (划分一组)例如，给定:

set={1,2,3}

结果应该是:

{ {{1,2,3}} , {{1},{2,3}} , {{1,2},{3}} , {{1,3},{2}}, {{1},{2},{3}}}

一组 n 元素的可能分区数是 B(n)，称为 Bell number .

到目前为止的代码:

public static <T> Set<Set<T>> powerSet(Set<T> myset) {
        Set<Set<T>> pset = new HashSet<Set<T>>();
        if (myset.isEmpty()) {
            pset.add(new HashSet<T>());
            return pset;
        }
        List<T> list = new ArrayList<T>(myset);
        T head = list.get(0);
        Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
        for (Set<T> set : powerSet(rest)) {
            Set<T> newSet = new HashSet<T>();
            newSet.add(head);
            newSet.addAll(set);
            pset.add(newSet);
            pset.add(set); 
        }

        return pset;
    }

输出数组的幂集:

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

Answer 1

最简单的解决方案是对集合的元素数量使用递归:构建一个构造 n 元素集合的所有分区的函数。对于 n+1 个元素，您可以将新元素添加到现有分区集中，或者将其放入自己的集合中。