## Generating integer partitions

### 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]
```

### Links

- Partition (Wikipedia)
- Partition.java (Wikipedia)
- Generating integer partitions (Jerome Kelleher)

## New Comment