An Algorithm for Generating Partitions

Exploring a small algorithm for generating different types of partitions from a list of items.

Overview

Sometimes it is useful in computing to partition a list of items into two or more parts. There are multiple ways one could split the items, by deciding which partitions should be considered equivelent. For example, when partitioning [A, B] into 2 parts, should [A B] be considered the same as [B A]?

Below are some interesting parameters that can configure how items could be partitioned. Ø denotes an empty part.

Parameter	Definition	Example when true for items=[A, B, C] and k=2
use_all	Whether or not to use all the items given as input	[A B] is a valid partitioning
unordered	Whether the partitions should be considered as sets, or if the order within a partition matters	[AB C] == [BA C]
unique	Whether the order of partitions within a partitioning is important	[AB C] == [C AB]
allow_empty	Whether the empty set can is considered a valid part	[ABC Ø] is a valid partitioning

Algorithm

Short and simple means of generating partitions with above parameters. There are more optimal ways to achieve similar results. In Python:

def partition(items, k, use_all=True, unordered=True, unique=True, allow_empty=True):
    """
    Partition and allocate items into k parts.

    items: list of not-None source elements
    k: number of partitions
    use_all: whether all elements of items should be used
    unordered: if the order of items in a partition is significant or not
    unique: whether the order of the partitions themselves is significant
    allow_empty: allow the empty-set as a part
    """

    result = [[] for _ in range(k)]

    def rec(num_used, last_src, last_dst):
        if not use_all or num_used == len(items):
            if not allow_empty and any(len(p) == 0 for p in result):
                yield from []
            else:
                yield [tuple(part) for part in result]

        for src in range(last_src if unordered else 0, len(items)):
            item = items[src]
            if item is not None:
                items[src] = None

                for dst in range(0 if unordered else last_dst, k):
                    result[dst].append(item)
                    yield from rec(num_used+1, src, dst)
                    result[dst].pop()

                    if unique and len(result[dst]) == 0:
                        break

                items[src] = item

    yield from rec(0, 0, 0)

Example

Take two items ['A', 'B'] and k=2 partitions

Note	allow_empty/use_all/unordered/unique	items	partitionings
	✅✅✅✅	2	[AB Ø] [A B]
	✅✅✅❌	4	[AB Ø] [A B] [B A] [Ø AB]
	✅✅❌✅	4	[AB Ø] [A B] [BA Ø] [B A]
	✅✅❌❌	6	[AB Ø] [A B] [Ø AB] [BA Ø] [B A] [Ø BA]
	✅❌✅✅	5	[Ø Ø] [A Ø] [AB Ø] [A B] [B Ø]
	✅❌✅❌	9	[Ø Ø] [A Ø] [AB Ø] [A B] [Ø A] [B A] [Ø AB] [B Ø] [Ø B]
	✅❌❌✅	7	[Ø Ø] [A Ø] [AB Ø] [A B] [B Ø] [BA Ø] [B A]
	✅❌❌❌	11	[Ø Ø] [A Ø] [AB Ø] [A B] [Ø A] [Ø AB] [B Ø] [BA Ø] [B A] [Ø B] [Ø BA]
1	❌✅✅✅	1	[A B]
	❌✅✅❌	2	[A B] [B A]
	❌✅❌✅	2	[A B] [B A]
	❌✅❌❌	2	[A B] [B A]
	❌❌✅✅	1	[A B]
	❌❌✅❌	2	[A B] [B A]
	❌❌❌✅	2	[A B] [B A]
	❌❌❌❌	2	[A B] [B A]

Set Theory

Some of the notions above are interesting from a computing point of view. The row marked (1) above meets the requirements of the mathematical notion of a set partition – distinct sets using all elements, no parts are the empty set, and order of elements within a part as well as order of parts within the partitioning irrelevant.

A Stirling number of the second kind \(S(n, k)\) denotes the number of ways a set with n-elements can be partitioned into k parts – it is possible using the definition to find this number without enumerating all possibilities. Summing \(S(n, i)\) for each i in 0..n gives the total ways a set with n-elements can be partitioned into any number of parts. This is also a Bell number – the total possible partitions of a set.