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.