获取集合的所有可能分区

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

在 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.