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.