DE → EN A-AA+ Sitemap Suche

## Generating integer partitions

Kommentare (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]
``````