How to Find All Partitions of a Set

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

generate all partitions of a set

You can try the recursive answer if your set is not to big (or else use stack) :

The principle is the following, you have a function that give back :

rec_func(SET) = List of List of Set

And work as follow :

rec_func(SET) =
  if SET = {empty}:
    // if no element, easy to give the answer
    return([[]])
  else:
    // 1. Remove one element from the set : 'a' to this set
    a = SET.pop()
    // 2. Call rec_func :
    list_of_list_of_set = rec_func(SET\'a')  
    response = []
    // 3. For every possibilities given by the function add the element 'a' :
    For every list_of_set in list_of_list_of_set  :
       // Case 1, you add 'a' to list_of_set
       response.push( [{'a'} + list_of_set] )
       // Case 2, for every set, you create a copy where you add 'a'
       for every set in list_of_set:
           response.push( [{set,'a'} + list_of_set\set] )

    // The function return the list of list of set created.        
    return(response)

Finding all partitions of a set in Java

You're very close to the right answer. You say you are getting infinite recursion, but in reality the program is running in an infinite loop in the outermost loop.

The primary difference from the Python code is that the i variable always advances in the outer loop in the Python version, but in your Java version, the i >>= 1 statement inside the inner loop always leaves i back at zero. The easy way to fix that is to simply use separate variables for the inner and outer loops.

In general, this is why it's a bad idea to try and directly translate a program from one language to another. Almost every program has some idioms that make sense in the original language that will be bizarre or meaningless in the target language. In particular, the Python code relies on implicit promotion to arbitrary precision integers for its correctness. This won't work well in Java, so the implementation below suffers from integer overflow if the input set is larger than 31 elements. Your example is only 4 elements, so for this specific case, it will produce the right answer.

Here's a corrected Java version:

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

public class Partition {
    private static List<List<List<String>>> partitions(List<String> inputSet) {
        List<List<List<String>>> res = new ArrayList<>();
        if (inputSet.isEmpty()) {
            List<List<String>> empty = new ArrayList<>();
            res.add(empty);
            return res;
        }
        // Note that this algorithm only works if inputSet.size() < 31
        // since you overflow int space beyond that. This is true even
        // if you use Math.pow and cast back to int. The original
        // Python code does not have this limitation because Python
        // will implicitly promote to a long, which in Python terms is
        // an arbitrary precision integer similar to Java's BigInteger.
        int limit = 1 << (inputSet.size() - 1);
        // Note the separate variable to avoid resetting
        // the loop variable on each iteration.
        for (int j = 0; j < limit; ++j) {
            List<List<String>> parts = new ArrayList<>();
            List<String> part1 = new ArrayList<>();
            List<String> part2 = new ArrayList<>();
            parts.add(part1);
            parts.add(part2);
            int i = j;
            for (String item : inputSet) {
                parts.get(i&1).add(item);
                i >>= 1;
            }
            for (List<List<String>> b : partitions(part2)) {
                List<List<String>> holder = new ArrayList<>();
                holder.add(part1);
                holder.addAll(b);
                res.add(holder);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        for (List<List<String>> partitions :
                 partitions(Arrays.asList("a", "b", "c", "d"))) {
            System.out.println(partitions);
        }
    }
}

Here's the output of my Java version:

[[a, b, c, d]]
[[b, c, d], [a]]
[[a, c, d], [b]]
[[c, d], [a, b]]
[[c, d], [b], [a]]
[[a, b, d], [c]]
[[b, d], [a, c]]
[[b, d], [c], [a]]
[[a, d], [b, c]]
[[a, d], [c], [b]]
[[d], [a, b, c]]
[[d], [b, c], [a]]
[[d], [a, c], [b]]
[[d], [c], [a, b]]
[[d], [c], [b], [a]]

How to find all partitions of a set (C++)

Long story short, introduce a variable ‘results’ for the returned list of lists, and initialize it at the start of the function. Then translate yield return x into results.Add(x), and translate yield break into return result.

There might be other ways to do it without taking up the memory to store results, but for sure they are difficult. Personally I love the mind-bending qualities of yield return. It is not too easy to explain succinctly but it is somewhat like pausing the executing method while you drop down on the stack to continue executing the calling function. When the calling function requests the next item in the iteration, you resume at the next statement after the yield return. I am sure that compiler people will groan at such an explanation but it works for me.

Find all unordered partitions of a list with a minimum number of elements

Here is one long-ish solution. No rejection is used in generating partitions, so in that sense this may be somewhat efficient. Still, there are lots of things to optimize.

Example:

list(get_partitions(range(3), 1))
# [[[0, 1, 2]], [[0], [1, 2]], [[1], [0, 2]], [[2], [0, 1]], [[0], [1], [2]]]

---

Here is an outline of how this works:

• First, it is useful to define a helper split function that takes a list lst and an integer n and return all ways to split the list into two groups, one of size n and another of size len(lst) - n.
• Second, we need to solve an easier version of the problem: how to split a list lst into n groups each of size k. Of course, this is only possible when len(lst) = n * k. This is implemented in get_partitions_same_size function. The idea is to always include the first element of lst in the first group and recurse.
• Third, we need to find all integer partitions of len(lst). I copied code from this thread.
• Fourth, for each integer partition p of len(lst), we need to find all ways to partition lst according to p.
  
  • For example, say len(lst) == 7 and p = 3 + 2 + 2. In this case, we can choose any three elements for the first group, any remaining two for the second group, and there is no choice to be made for the final third group.
  • This can introduce redundancy as we can get two partitions that only differ in the order of the last two groups.
  • To deal with this issue, we can represent a partition by counting the number of groups of each size. In this example, p corresponds to p_scheme = [(3, 1), (2, 2)]. The function get_partitions_helper takes in a list lst and a "partition scheme" p_scheme, and returns all corresponding partitions without double-counting. This is where get_partitions_same_size from step two is used.
• Finally, everything comes together in get_partitions: we loop over integer partitions of len(lst) and return all possible list partitions corresponding to each possible integer partition.

This is a fun problem and comments on bugs and optimizations are very welcome.

---

from itertools import combinations
from collections import Counter

# from this thread:
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning
def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p


def split(lst, n):
  '''
  return all ways to split lst into two groups, 
  with n and len(lst) - n elements respectively
  '''
  assert len(lst) >= n
  # handle special case of len(lst) == 2 * n
  if len(lst) == 2 * n:
    for first, second in split(lst[1:], n-1):
      yield [lst[0], *first], second
  else:
    for comb in combinations(range(len(lst)), n):
      comb = set(comb)
      first = [x for i, x in enumerate(lst) if i in comb]
      second = [x for i, x in enumerate(lst) if i not in comb]
      yield first, second


def get_partitions_same_size(lst, n, k):
  # print(lst, n, k)
  'return all ways to partition lst into n parts each of size k up to order'
  if len(lst) != n * k:
    print(lst, n, k)
  assert len(lst) == n * k
  if n == 0 and len(lst) == 0:
    yield []
  # case when group size is one
  elif k == 1:
    yield [[x] for x in lst]
  # otherwise, without loss, the first element of lst goes into the first group
  else:
    for first, rest in split(lst[1:], k-1):
      for rec_call in get_partitions_same_size(rest, n-1, k):
        yield [[lst[0], *first], *rec_call]


def get_partitions_helper(lst, p_scheme):
  """
  return all ways to partition lst into groups according to a partition scheme p_scheme

  p_scheme describes an integer partition of len(lst)
  for example, if len(lst) == 5, then possible integer partitions are:
  [(5,), (1, 4), (1, 1, 3), (1, 1, 1, 2), (1, 1, 1, 1, 1), (1, 2, 2), (2, 3)]
  for each, we count the number of groups of a given size
  the corresponding partition schemes are:
  [[(5, 1)],
  [(1, 1), (4, 1)],
  [(1, 2), (3, 1)],
  [(1, 3), (2, 1)],
  [(1, 5)],
  [(1, 1), (2, 2)],
  [(2, 1), (3, 1)]]
  """
  if not lst and not p_scheme:
    yield []
    return 
  assert len(lst) == sum(a * b for a, b in p_scheme)
  group_size, group_count = p_scheme[0]
  num_elts = group_size * group_count
  for first, second in split(lst, num_elts):
    for firsts in get_partitions_same_size(first, group_count, group_size):
      for seconds in get_partitions_helper(second, p_scheme[1:]):
        yield [*firsts, *seconds]


def get_partitions(lst, min_):
  """
  get all partitions of lst into groups s.t. each group has at least min_ elements
  up to order (of groups and elements within a group)
  """
  for partition in partitions(len(lst), min_):
    p_scheme = list(Counter(partition).items())
    yield from get_partitions_helper(lst, p_scheme)

Recursively finding all partitions of a set of n objects into k non-empty subsets

If you can read Python code, consider the next algorithm which I've quickly adapted from my implementation of set partition into equal size parts.

Recursive function fills K parts with N values.

The lastfilled parameter helps to avoid duplicates - it provides an increasing sequence of leading (smallest) elements of every part.

The empty parameter is intended to avoid empty parts.

def genp(parts:list, empty, n, k, m, lastfilled):
    if m == n:
        print(parts)
        global c
        c+=1
        return
    if n - m == empty:
        start = k - empty
    else:
        start = 0
    for i in range(start, min(k, lastfilled + 2)):
        parts[i].append(m)
        if len(parts[i]) == 1:
            empty -= 1
        genp(parts, empty, n, k, m+1, max(i, lastfilled))
        parts[i].pop()
        if len(parts[i]) == 0:
            empty += 1


def setkparts(n, k):
    parts = [[] for _ in range(k)]
    cnts = [0]*k
    genp(parts, k, n, k, 0, -1)

c = 0
setkparts(5,3)
#setkparts(7,5)
print(c)

[[0, 1, 2], [3], [4]]
[[0, 1, 3], [2], [4]]
[[0, 1], [2, 3], [4]]
[[0, 1, 4], [2], [3]]
[[0, 1], [2, 4], [3]]
[[0, 1], [2], [3, 4]]
[[0, 2, 3], [1], [4]]
[[0, 2], [1, 3], [4]]
[[0, 2, 4], [1], [3]]
[[0, 2], [1, 4], [3]]
[[0, 2], [1], [3, 4]]
[[0, 3], [1, 2], [4]]
[[0], [1, 2, 3], [4]]
[[0, 4], [1, 2], [3]]
[[0], [1, 2, 4], [3]]
[[0], [1, 2], [3, 4]]
[[0, 3, 4], [1], [2]]
[[0, 3], [1, 4], [2]]
[[0, 3], [1], [2, 4]]
[[0, 4], [1, 3], [2]]
[[0], [1, 3, 4], [2]]
[[0], [1, 3], [2, 4]]
[[0, 4], [1], [2, 3]]
[[0], [1, 4], [2, 3]]
[[0], [1], [2, 3, 4]]
25

---

Related Topics