How to find all partitions of a set
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());
}
}
}
}
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