How to find all partitions of a set

Question

I have a set of distinct values. I am looking for a way to generate all partitions of this set, i.e. all possible ways of dividing the set into subsets.

For instance, the set {1, 2, 3} has the following partitions:

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

As these are sets in the mathematical sense, order is irrelevant. For instance, {1, 2}, {3} is the same as {3}, {2, 1} and should not be a separate result.

A thorough definition of set partitions can be found on Wikipedia.

Answer 1

Please refer to the Bell number, here is a brief thought to this problem:
consider f(n,m) as partition a set of n element into m non-empty sets.

For example, the partition of a set of 3 elements can be:
1) set size 1: {{1,2,3}, } <-- f(3,1)
2) set size 2: {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}} <-- f(3,2)
3) set size 3: {{1}, {2}, {3}} <-- f(3,3)

Now let's calculate f(4,2):
there are two ways to make f(4,2):

A. add a set to f(3,1), which will convert from {{1,2,3}, } to {{1,2,3}, {4}}
B. add 4 to any of set of f(3,2), which will convert from
{{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}}
to
{{1,2,4},{3}}, {{1,2},{3,4}}
{{1,3,4},{2}}, {{1,3},{2,4}}
{{2,3,4},{1}}, {{2,3},{1,4}}

So f(4,2) = f(3,1) + f(3,2)*2
which result in f(n,m) = f(n-1,m-1) + f(n-1,m)*m

Here is Java code for get all partitions of set:

import java.util.ArrayList;
import java.util.List;

public class SetPartition {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for(int i=1; i<=3; i++) {
            list.add(i);
        }

        int cnt = 0;
        for(int i=1; i<=list.size(); i++) {
            List<List<List<Integer>>> ret = helper(list, i);
            cnt += ret.size();
            System.out.println(ret);
        }
        System.out.println("Number of partitions: " + cnt);
    }

    // partition f(n, m)
    private static List<List<List<Integer>>> helper(List<Integer> ori, int m) {
        List<List<List<Integer>>> ret = new ArrayList<>();
        if(ori.size() < m || m < 1) return ret;

        if(m == 1) {
            List<List<Integer>> partition = new ArrayList<>();
            partition.add(new ArrayList<>(ori));
            ret.add(partition);
            return ret;
        }

        // f(n-1, m)
        List<List<List<Integer>>> prev1 = helper(ori.subList(0, ori.size() - 1), m);
        for(int i=0; i<prev1.size(); i++) {
            for(int j=0; j<prev1.get(i).size(); j++) {
                // Deep copy from prev1.get(i) to l
                List<List<Integer>> l = new ArrayList<>();
                for(List<Integer> inner : prev1.get(i)) {
                    l.add(new ArrayList<>(inner));
                }

                l.get(j).add(ori.get(ori.size()-1));
                ret.add(l);
            }
        }

        List<Integer> set = new ArrayList<>();
        set.add(ori.get(ori.size() - 1));
        // f(n-1, m-1)
        List<List<List<Integer>>> prev2 = helper(ori.subList(0, ori.size() - 1), m - 1);
        for(int i=0; i<prev2.size(); i++) {
            List<List<Integer>> l = new ArrayList<>(prev2.get(i));
            l.add(set);
            ret.add(l);
        }

        return ret;
    }

}

And result is:
[[[1, 2, 3]]] [[[1, 3], [2]], [[1], [2, 3]], [[1, 2], [3]]] [[[1], [2], [3]]] Number of partitions: 5

Answer 2

Here is a solution in Ruby that's about 20 lines long:

def copy_2d_array(array)
  array.inject([]) {|array_copy, item| array_copy.push(item)}
end

#
# each_partition(n) { |partition| block}
#
# Call the given block for each partition of {1 ... n}
# Each partition is represented as an array of arrays.
# partition[i] is an array indicating the membership of that partition.
#
def each_partition(n)
  if n == 1
    # base case:  There is only one partition of {1}
    yield [[1]]
  else
    # recursively generate the partitions of {1 ... n-1}.
    each_partition(n-1) do |partition|
      # adding {n} to a subset of partition generates
      # a new partition of {1 ... n}
      partition.each_index do |i|
        partition_copy = copy_2d_array(partition)
        partition_copy[i].push(n)
        yield (partition_copy)    
      end # each_index

      # Also adding the set {n} to a partition of {1 ... n}
      # generates a new partition of {1 ... n}
      partition_copy = copy_2d_array(partition)
      partition_copy.push [n]
      yield(partition_copy)
    end # block for recursive call to each_partition
  end # else
end # each_partition

(I'm not trying to shill for Ruby, I just figured that this solution may easier for some readers to understand.)

Answer 3

Just for fun, here's a shorter purely iterative version:

public static IEnumerable<List<List<T>>> GetAllPartitions<T>(T[] elements) {
    var lists = new List<List<T>>();
    var indexes = new int[elements.Length];
    lists.Add(new List<T>());
    lists[0].AddRange(elements);
    for (;;) {
        yield return lists;
        int i,index;
        for (i=indexes.Length-1;; --i) {
            if (i<=0)
                yield break;
            index = indexes[i];
            lists[index].RemoveAt(lists[index].Count-1);
            if (lists[index].Count>0)
                break;
            lists.RemoveAt(index);
        }
        ++index;
        if (index >= lists.Count)
            lists.Add(new List<T>());
        for (;i<indexes.Length;++i) {
            indexes[i]=index;
            lists[index].Add(elements[i]);
            index=0;
        }
    }

Test here:https://ideone.com/EccB5n

And a simpler recursive version:

public static IEnumerable<List<List<T>>> GetAllPartitions<T>(T[] elements, int maxlen) {
    if (maxlen<=0) {
        yield return new List<List<T>>();
    }
    else {
        T elem = elements[maxlen-1];
        var shorter=GetAllPartitions(elements,maxlen-1);
        foreach (var part in shorter) {
            foreach (var list in part.ToArray()) {
                list.Add(elem);
                yield return part;
                list.RemoveAt(list.Count-1);
            }
            var newlist=new List<T>();
            newlist.Add(elem);
            part.Add(newlist);
            yield return part;
            part.RemoveAt(part.Count-1);
        }
    }

https://ideone.com/Kdir4e

Answer 4

A trick I used for a set of N members. 1. Calculate 2^N 2. Write each number between 1 and N in binary. 3. You will get 2^N binary numbers each of length N and each number tells you how to split the set into subset A and B. If the k'th digit is 0 then put the k'th element in set A otherwise put it in set B.

Answer 5

I've found a straightforward recursive solution.

First, let's solve a simpler problem: how to find all partitions consisting of exactly two parts. For an n-element set, we can count an int from 0 to (2^n)-1. This creates every n-bit pattern, with each bit corresponding to one input element. If the bit is 0, we place the element in the first part; if it is 1, the element is placed in the second part. This leaves one problem: For each partition, we'll get a duplicate result where the two parts are swapped. To remedy this, we'll always place the first element into the first part. We then only distribute the remaining n-1 elements by counting from 0 to (2^(n-1))-1.

Now that we can partition a set into two parts, we can write a recursive function that solves the rest of the problem. The function starts off with the original set and finds all two-part-partitions. For each of these partitions, it recursively finds all ways to partition the second part into two parts, yielding all three-part partitions. It then divides the last part of each of these partitions to generate all four-part partitions, and so on.

The following is an implementation in C#. Calling

Partitioning.GetAllPartitions(new[] { 1, 2, 3, 4 })

yields

{ {1, 2, 3, 4} },
{ {1, 3, 4}, {2} },
{ {1, 2, 4}, {3} },
{ {1, 4}, {2, 3} },
{ {1, 4}, {2}, {3} },
{ {1, 2, 3}, {4} },
{ {1, 3}, {2, 4} },
{ {1, 3}, {2}, {4} },
{ {1, 2}, {3, 4} },
{ {1, 2}, {3}, {4} },
{ {1}, {2, 3, 4} },
{ {1}, {2, 4}, {3} },
{ {1}, {2, 3}, {4} },
{ {1}, {2}, {3, 4} },
{ {1}, {2}, {3}, {4} }.

using System;
using System.Collections.Generic;
using System.Linq;

namespace PartitionTest {
    public static class Partitioning {
        public static IEnumerable<T[][]> GetAllPartitions<T>(T[] elements) {
            return GetAllPartitions(new T[][]{}, elements);
        }

        private static IEnumerable<T[][]> GetAllPartitions<T>(
            T[][] fixedParts, T[] suffixElements)
        {
            // A trivial partition consists of the fixed parts
            // followed by all suffix elements as one block
            yield return fixedParts.Concat(new[] { suffixElements }).ToArray();

            // Get all two-group-partitions of the suffix elements
            // and sub-divide them recursively
            var suffixPartitions = GetTuplePartitions(suffixElements);
            foreach (Tuple<T[], T[]> suffixPartition in suffixPartitions) {
                var subPartitions = GetAllPartitions(
                    fixedParts.Concat(new[] { suffixPartition.Item1 }).ToArray(),
                    suffixPartition.Item2);
                foreach (var subPartition in subPartitions) {
                    yield return subPartition;
                }
            }
        }

        private static IEnumerable<Tuple<T[], T[]>> GetTuplePartitions<T>(
            T[] elements)
        {
            // No result if less than 2 elements
            if (elements.Length < 2) yield break;

            // Generate all 2-part partitions
            for (int pattern = 1; pattern < 1 << (elements.Length - 1); pattern++) {
                // Create the two result sets and
                // assign the first element to the first set
                List<T>[] resultSets = {
                    new List<T> { elements[0] }, new List<T>() };
                // Distribute the remaining elements
                for (int index = 1; index < elements.Length; index++) {
                    resultSets[(pattern >> (index - 1)) & 1].Add(elements[index]);
                }

                yield return Tuple.Create(
                    resultSets[0].ToArray(), resultSets[1].ToArray());
            }
        }
    }
}

Answer 6

Here is a non-recursive solution

class Program
{
    static void Main(string[] args)
    {
        var items = new List<Char>() { 'A', 'B', 'C', 'D', 'E' };
        int i = 0;
        foreach (var partition in items.Partitions())
        {
            Console.WriteLine(++i);
            foreach (var group in partition)
            {
                Console.WriteLine(string.Join(",", group));
            }
            Console.WriteLine();
        }
        Console.ReadLine();
    }
}  

public static class Partition
{
    public static IEnumerable<IList<IList<T>>> Partitions<T>(this IList<T> items)
    {
        if (items.Count() == 0)
            yield break;
        var currentPartition = new int[items.Count()];
        do
        {
            var groups = new List<T>[currentPartition.Max() + 1];
            for (int i = 0; i < currentPartition.Length; ++i)
            {
                int groupIndex = currentPartition[i];
                if (groups[groupIndex] == null)
                    groups[groupIndex] = new List<T>();
                groups[groupIndex].Add(items[i]);
            }
            yield return groups;
        } while (NextPartition(currentPartition));
    }

    private static bool NextPartition(int[] currentPartition)
    {
        int index = currentPartition.Length - 1;
        while (index >= 0)
        {
            ++currentPartition[index];
            if (Valid(currentPartition))
                return true;
            currentPartition[index--] = 0;
        }
        return false;
    }

    private static bool Valid(int[] currentPartition)
    {
        var uniqueSymbolsSeen = new HashSet<int>();
        foreach (var item in currentPartition)
        {
            uniqueSymbolsSeen.Add(item);
            if (uniqueSymbolsSeen.Count <= item)
                return false;
        }
        return true;
    }
}