Get all possible partitions of a set

Question

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}

the result should be:

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

the number of possible partition of a set of n elements is B(n) known as Bell number.

The code so far:

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;
    }

which outputs the powerset of the the array :

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

Answer 1

The easiest solution is using recursion on the number of elements of your set: Build a function that constructs all partitions of an n-element set. For n+1 elements, you either add the new element to of the existing partition sets, or put it in a set of its own.

Answer 2

A solution for the searched algorithm would be:

In Pseudocode:

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);
                }
            }
        }
    }

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;
    }
}

The generated output is:

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.

Answer 3

First, the powerset:

For n distinct elements, you can create 2ⁿ sets which can easily shown when considering the question “is this element included in this particular set?” a boolean value:

For n=3:

0: 0 0 0   none included
1: 0 0 1   first included
2: 0 1 0   second included
3: 0 1 1   first and second one included
4: 1 0 0   third included
5: 1 0 1   first and third included
6: 1 1 0   second and third included
7: 1 1 1   all included

So iterating over all combinations can be implemented by iterating over integer numbers from 0 to 2ⁿ and using the bit pattern of each number to select the elements from the original set (we have to copy them into an ordered structure like a List for that):

public static <T> Set<Set<T>> allPermutations(Set<T> input) {

    List<T> sequence = new ArrayList<>(input);
    long count = sequence.size() > 62? Long.MAX_VALUE: 1L << sequence.size();

    HashSet<Set<T>> result = new HashSet<>((int)Math.min(Integer.MAX_VALUE, count));

    for(long l = 0; l >= 0 && l < count; l++) {
        if(l == 0) result.add(Collections.emptySet());
        else if(Long.lowestOneBit(l) == l)
            result.add(Collections.singleton(sequence.get(Long.numberOfTrailingZeros(l))));
        else {
            HashSet<T> next = new HashSet<>((int)(Long.bitCount(l)*1.5f));
            for(long tmp = l; tmp != 0; tmp-=Long.lowestOneBit(tmp)) {
                next.add(sequence.get(Long.numberOfTrailingZeros(tmp)));
            }
            result.add(next);
        }
    }
    return result;
}

Then

Set<String> input = new HashSet<>();
Collections.addAll(input, "1", "2", "3");
System.out.println(allPermutations(input));

gives us

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

---

To utilize this for identifying the partitions, we have to expand the logic to use the counter’s bits to select bits from another mask, which will identify the actual elements to include. Then, we can re-use the same operation to get the partitions of the elements not included so far, using a simple binary not operation:

public static <T> Set<Set<Set<T>>> allPartitions(Set<T> input) {
    List<T> sequence = new ArrayList<>(input);
    if(sequence.size() > 62) throw new OutOfMemoryError();
    return allPartitions(sequence, (1L << sequence.size()) - 1);
}
private static <T> Set<Set<Set<T>>> allPartitions(List<T> input, long bits) {
    long count = 1L << Long.bitCount(bits);

    if(count == 1) {
        return Collections.singleton(new HashSet<>());
    }

    Set<Set<Set<T>>> result = new HashSet<>();

    for(long l = 1; l >= 0 && l < count; l++) {
        long select = selectBits(l, bits);
        final Set<T> first = get(input, select);
        for(Set<Set<T>> all: allPartitions(input, bits&~select)) {
            all.add(first);
            result.add(all);
        }
    }
    return result;
}
private static long selectBits(long selected, long mask) {
    long result = 0;
    for(long bit; selected != 0; selected >>>= 1, mask -= bit) {
        bit = Long.lowestOneBit(mask);
        if((selected & 1) != 0) result |= bit;
    }
    return result;
}
private static <T> Set<T> get(List<T> elements, long bits) {
    if(bits == 0) return Collections.emptySet();
    else if(Long.lowestOneBit(bits) == bits)
        return Collections.singleton(elements.get(Long.numberOfTrailingZeros(bits)));
    else {
        HashSet<T> next = new HashSet<>();
        for(; bits != 0; bits-=Long.lowestOneBit(bits)) {
            next.add(elements.get(Long.numberOfTrailingZeros(bits)));
        }
        return next;
    }
}

Then,

    Set<String> input = new HashSet<>();
    Collections.addAll(input, "1", "2", "3");
    System.out.println(allPartitions(input));

gives us

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

whereas

Set<String> input = new HashSet<>();
Collections.addAll(input, "1", "2", "3", "4");
for(Set<Set<String>> partition: allPartitions(input))
    System.out.println(partition);

yields

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