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 notNone 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 emptyset 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 nelements 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 nelements can be partitioned into any number of parts. This is also a Bell number – the total possible partitions of a set.