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.

Pyro

I can't say I have come across this question yet and some searching doesn't provide an adequate answer either, +1. At first sight the code seems alright as well (definitely more concise than anything I've come across that gets close to the intention), +1 from me. – Exotic

See https://mcmap.net/q/190640/-set-partitions-in-python/281545 for the python version – Samy

Answer 1

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

Pyro

wow, that's cool. you can answer your own question? i never thought of that. – Malvern

Thanks, that's a brilliant solution, you made my day! Here's my JS ES6 implementation. I was searching for this exact problem, all the combinations of sets you can split a set into, I couldn't find anything until I understood was the technical term was: set partition. – Wanda

Answer 2

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

Geminius

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

Zonnya

I tried both and the recursive solution is impressively fast. Just a bit of warning: the contents of each returned partition are only valid at the moment of enumeration. As soon as another partition is enumerated, the contents of the previous one are cleared. – Feathercut

how might I port this to C++. C++ lacks the yield keyword – Crouton

okay i ported it to C++ #59959203 – Crouton

Answer 4

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

Townspeople

Answer 5

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

Selflove

Answer 6

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.

Vedetta

Careful, this only finds 2-partitions, i.e. partitions of the set into 2 subsets. In the original example, this ignores { {1}, {2}, {3} }. – Diddle

Answer 7

I have implemented Donald Knuth's very nice Algorith H that lists all partitions in Matlab

https://uk.mathworks.com/matlabcentral/fileexchange/62775-allpartitions--s-- http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz

function [ PI, RGS ] = AllPartitions( S )
    %% check that we have at least two elements
    n = numel(S);
    if n < 2
        error('Set must have two or more elements');
    end    
    %% Donald Knuth's Algorith H
    % restricted growth strings
    RGS = [];
    % H1
    a = zeros(1,n);
    b = ones(1,n-1);
    m = 1;
    while true
        % H2
        RGS(end+1,:) = a;
        while a(n) ~= m            
            % H3
            a(n) = a(n) + 1;
            RGS(end+1,:) = a;
        end
        % H4
        j = n - 1;
        while a(j) == b(j)
           j = j - 1; 
        end
        % H5
        if j == 1
            break;
        else
            a(j) = a(j) + 1;
        end
        % H6
        m = b(j) + (a(j) == b (j));
        j = j + 1;
        while j < n 
            a(j) = 0;
            b(j) = m;
            j = j + 1;
        end
        a(n) = 0;
    elementsd
    %% get partitions from the restricted growth stirngs
    PI = PartitionsFromRGS(S, RGS);
end

Predicative

Link is broken? – Samy

Answer 8

Here is a slight variation on the recursive version mentioned in this answer which use Linq.

        public static IEnumerable<T[][]> GetAllPartitions<T>(IEnumerable<T> elements)
        {
            if (elements.IsEmpty())
            {
                yield return Array.Empty<T[]>();
                yield break;
            }

            T lastElt = elements.Last();
            var setWithLastElt = new[] { lastElt };

            foreach (var smallerPartition in GetAllPartitions(elements.SkipLast(1)))
            {
                foreach (var subSet in smallerPartition)
                {
                    yield return smallerPartition.Except(subSet)
                                                 .Append(subSet.Append(lastElt).ToArray())
                                                 .ToArray();
                }

                yield return smallerPartition.Append(setWithLastElt)
                                             .ToArray();
            }
        }

Why

Answer 9

def allPossiblePartitions(l): # l is the list whose possible partitions have to be found


    # to get all possible partitions, we consider the binary values from 0 to 2**len(l))//2-1
    """
    {123}       --> 000 (0)
    {12} {3}    --> 001 (1)
    {1} {2} {3} --> 010 (2)
    {1} {23}    --> 011 (3)  --> (0 to (2**3//2)-1)

    iterate over each possible partitions, 
    if there are partitions>=days and
    if that particular partition contains
    more than one element then take max of all elements under that partition
    ex: if the partition is {1} {23} then we take 1+3
    """
    for i in range(0,(2**len(l))//2):
            s = bin(i).replace('0b',"")
            s = '0'*(len(l)-len(s)) + s
            sublist = []
            prev = s[0]
            partitions = []
            k = 0
            for i in s:
                if (i == prev):
                    partitions.append(l[k])
                    k+=1
                else:
                    sublist.append(partitions)
                    partitions = [l[k]]
                    k+=1
                    prev = i
            sublist.append(partitions)
            print(sublist)

Ardy

While this code may solve the question, including an explanation of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. Please edit your answer to add explanations and give an indication of what limitations and assumptions apply. – Endamage

@user13052579, your technique is not exhaustive. allPossiblePartitions([ABC]) misses [[AC], [B]] See Spiralmoon's solution above ... From the Bell numbers, there should be 15 enumerated partitions for N = 4, but your technique, allPossiblePartitions([ABCD]), yields 8. Missing: [[AC],[B],[D]]; [[AD],[B],[C]]; [[A],[BD],[C]]; [[ABD],[C]]; [[ACD],[B]]. – Delius

For N = 4 there are 4 partitions having a set with one element, and a set of 3 elements, but allPossiblePartitions() provides only two of them. If your algorithm is working, it should return the Bell number for the given list size. – Delius