获取集合中所有可能的分区 [英] Get all possible partitions of a set

问题描述

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

这篇关于获取集合中所有可能的分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！