获取集合的所有可能分区 [英] 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屋！