Blog - Post

Generating integer partitions

30-Sep-2020Comments (0)

Simple recursive Python programs for generating partitions of an integer.

Introduction

Wikipedia: In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be partitioned in five distinct ways: 4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Basic program printing partitions

def partition1_rec(n, k, prefix):
	# Partitions of n with all values less than or equal to k
	# The partition is accumulated in prefix
	if n == 0:
		print(prefix)
		return  
	for i in range(1, min(k, n) + 1):
		partition1_rec(n - i, i, prefix + " " + str(i))
		
		
def partition1(n, k):
	# Partitions of n with all values less than or equal to k
	partition1_rec(n, k, "")
		
# Test: partitions of 4 with all values less than or equal to 2
partition1(4, 2)
# Result:
# 1 1 1 1
# 2 1 1
# 2 2

# Test: all partitions of 4
partition1(4, 4)
# Result:
# 1 1 1 1
# 2 1 1
# 2 2
# 3 1
# 4

Idea:
Let p(n, k) be the partitions of n with all values less or equal to k. We have:
p(n, k):
1 + p(n - 1, k) = 1 plus partitions of n minus 1
2 + p(n - 2, k) = 2 plus partitions of n minus 2
...
k + p(n - k, k) = k plus partitions of n minus k

Program returning list of partitions

def partition2(n, k):
	parts = []
	partition2_rec(n, k, [], parts)
	return parts

def partition2_rec(n, k, part, parts):
	# part = one accumulated partition
	# parts = list of all partitions
	if n == 0:
		parts.append(part) 
		return
	for i in range(1, min(k, n) + 1):
		partition2_rec(n - i, i, part + [i], parts)

# Test:
print(partition2(4, 2))

# Result:
# [[1, 1, 1, 1], [2, 1, 1], [2, 2]]

Program returning list of partitions (without accumulator)

def partition3(n, k):
	if n == 0:
		return [[]]
	partitions = []
	for i in range(1, min(k, n) + 1):
		parts = partition3(n - i, i)
		for p in parts:
			partitions.append([i] + p)
	return partitions

# Test:
print(partition3(4, 2))

# Result:
# [[1, 1, 1, 1], [2, 1, 1], [2, 2]]

Partitions in descending order

The above programs generate partitions is ascending order. To generate partitions in descending order only the orderof the for-loop needs to be reversed.

Efficient iterative alorithms

The above programs are well understandable but less efficient due to the inherent recursion. Very efficient iterative algorithms are presented by Jerome Kelleher. I include one of his comprehensible algorithms here:

def rule_asc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    a[1] = n
    while k != 0:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while x <= y:
            a[k] = x
            y -= x
            k += 1
        a[k] = x + y
        yield a[:k + 1]