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)
Neuer Kommentar