获取集合中所有可能的分区

本文介绍了获取集合中所有可能的分区的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在Java中，我有一个集合，我想在其中获得所有可能的子集组合，它们的并集构成主集。 （划分集合），例如：

In Java I have a set where I want to obtain all possible combinations of subsets which their union make the main set. (partitioning a set) for example, given:

set={1,2,3}

结果应为：

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

可能的分区数一组 n 元素中的一个是 B（n），称为电话号码。

the number of possible partition of a set of n elements is B(n) known as 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]]

推荐答案

一种解决方案所搜索的算法将是：

A solution for the searched algorithm would be:

在伪代码中：

Set<T> base; //the base set Set<Set<T>> pow; //the power set Set<Set<Set<T>>> parts; //the partitions set function findAllPartSets(): pow = power set of base if (pow.length > 1) { pow.remove(empty set); } for p in pow: findPartSets(p); function findPartSets(Set<Set<T>> current): maxLen = base.length - summed length of all sets in current; if (maxLen == 0) { parts.add(current); return; } else { for i in 1 to maxLen { for s in pow { if (s.length == i && !(any of s in current)) { Set<Set<T>> s2 = new Set(current, s); findPartSets(s2); } } } }

或在Java中的实现（使用类而不是静态函数）：

Or the implementation in java (using a class instead of a static function):

package partitionSetCreator; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class PartitionSetCreator<T> { private Set<Set<Set<T>>> parts;//the partitions that are created private Set<Set<T>> pow;//the power set of the input set private Set<T> base;//the base set /** * The main method is just for testing and can be deleted. */ public static void main(String[] args) { //test using an empty set = [] Set<Integer> baseSet = new HashSet<Integer>(); PartitionSetCreator<Integer> partSetCreatorEmpty = new PartitionSetCreator<Integer>(baseSet); Set<Set<Set<Integer>>> partitionSetsEmpty = partSetCreatorEmpty.findAllPartitions(); System.out.println("BaseSet: " + baseSet); System.out.println("Result: " + partitionSetsEmpty); System.out.println("Base-Size: " + baseSet.size() + " Result-Size: " + partitionSetsEmpty.size()); //test using base set = [1] baseSet.add(1); PartitionSetCreator<Integer> partSetCreator = new PartitionSetCreator<Integer>(baseSet); Set<Set<Set<Integer>>> partitionSets = partSetCreator.findAllPartitions(); System.out.println("BaseSet: " + baseSet); System.out.println("Result: " + partitionSets); System.out.println("Base-Size: " + baseSet.size() + " Result-Size: " + partitionSets.size()); //test using base set = [1, 2] baseSet.add(2); PartitionSetCreator<Integer> partSetCreator2 = new PartitionSetCreator<Integer>(baseSet); Set<Set<Set<Integer>>> partitionSets2 = partSetCreator2.findAllPartitions(); System.out.println("BaseSet: " + baseSet); System.out.println("Result: " + partitionSets2); System.out.println("Base-Size: " + baseSet.size() + " Result-Size: " + partitionSets2.size()); //another test using base set = [1, 2, 3] baseSet.add(3); PartitionSetCreator<Integer> partSetCreator3 = new PartitionSetCreator<Integer>(baseSet); Set<Set<Set<Integer>>> partitionSets3 = partSetCreator3.findAllPartitions(); System.out.println("BaseSet: " + baseSet); System.out.println("Result: " + partitionSets3); System.out.println("Base-Size: " + baseSet.size() + " Result-Size: " + partitionSets3.size()); //another test using base set = [1, 2, 3, 4] baseSet.add(4); PartitionSetCreator<Integer> partSetCreator4 = new PartitionSetCreator<Integer>(baseSet); Set<Set<Set<Integer>>> partitionSets4 = partSetCreator4.findAllPartitions(); System.out.println("BaseSet: " + baseSet); System.out.println("Result: " + partitionSets4); System.out.println("Base-Size: " + baseSet.size() + " Result-Size: " + partitionSets4.size()); } public PartitionSetCreator(Set<T> base) { this.base = base; this.pow = powerSet(base); if (pow.size() > 1) { //remove the empty set if it's not the only entry in the power set pow.remove(new HashSet<T>()); } this.parts = new HashSet<Set<Set<T>>>(); } /** * Calculation is in this method. */ public Set<Set<Set<T>>> findAllPartitions() { //find part sets for every entry in the power set for (Set<T> set : pow) { Set<Set<T>> current = new HashSet<Set<T>>(); current.add(set); findPartSets(current); } //return all partitions that were found return parts; } /** * Finds all partition sets for the given input and adds them to parts (global variable). */ private void findPartSets(Set<Set<T>> current) { int maxLen = base.size() - deepSize(current); if (maxLen == 0) { //the current partition is full -> add it to parts parts.add(current); //no more can be added to current -> stop the recursion return; } else { //for all possible lengths for (int i = 1; i <= maxLen; i++) { //for every entry in the power set for (Set<T> set : pow) { if (set.size() == i) { //the set from the power set has the searched length if (!anyInDeepSet(set, current)) { //none of set is in current Set<Set<T>> next = new HashSet<Set<T>>(); next.addAll(current); next.add(set); //next = current + set findPartSets(next); } } } } } } /** * Creates a power set from the base set. */ private Set<Set<T>> powerSet(Set<T> base) { Set<Set<T>> pset = new HashSet<Set<T>>(); if (base.isEmpty()) { pset.add(new HashSet<T>()); return pset; } List<T> list = new ArrayList<T>(base); 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; } /** * The summed up size of all sub-sets */ private int deepSize(Set<Set<T>> set) { int deepSize = 0; for (Set<T> s : set) { deepSize += s.size(); } return deepSize; } /** * Checks whether any of set is in any of the sub-sets of current */ private boolean anyInDeepSet(Set<T> set, Set<Set<T>> current) { boolean containing = false; for (Set<T> s : current) { for (T item : set) { containing |= s.contains(item); } } return containing; } }

生成的输出为：

BaseSet: [] Result: [[[]]] Base-Size: 0 Result-Size: 1 BaseSet: [1] Result: [[[1]]] Base-Size: 1 Result-Size: 1 BaseSet: [1, 2] Result: [[[1], [2]], [[1, 2]]] Base-Size: 2 Result-Size: 2 BaseSet: [1, 2, 3] Result: [[[1], [2], [3]], [[1], [2, 3]], [[2], [1, 3]], [[1, 2], [3]], [[1, 2, 3]]] Base-Size: 3 Result-Size: 5 BaseSet: [1, 2, 3, 4] Result: [[[1], [2], [3], [4]], [[1], [2], [3, 4]], [[4], [1, 2, 3]], [[1], [3], [2, 4]], [[1, 2, 3, 4]], [[1], [4], [2, 3]], [[1], [2, 3, 4]], [[2], [3], [1, 4]], [[2], [4], [1, 3]], [[2], [1, 3, 4]], [[1, 3], [2, 4]], [[1, 2], [3], [4]], [[1, 2], [3, 4]], [[3], [1, 2, 4]], [[1, 4], [2, 3]]] Base-Size: 4 Result-Size: 15

创建的输出与您要求的预期输出类似，除了以下内容中没有空集解决方案（输入集为空时除外）。 因此，集合的生成分区和集合的分区数量现在符合响铃号码。

The output that is created is similar to the expected output you were asking for except that there is no empty set in any of the solutions (except when the input set is empty). So the generated partitions of the set and the number of partitions of a set are now compliant with the Bell Numbers.