dynamic_programming.integer_partition

The number of partitions of a number n into at least k parts equals the number of partitions into exactly k parts plus the number of partitions into at least k-1 parts. Subtracting 1 from each part of a partition of n into k parts gives a partition of n-k into k parts. These two facts together are used for this algorithm. * https://en.wikipedia.org/wiki/Partition_(number_theory) * https://en.wikipedia.org/wiki/Partition_function_(number_theory)

Attributes

n

Functions

partition(→ int)

Module Contents

dynamic_programming.integer_partition.partition(m: int) → int

>>> partition(5)
7
>>> partition(7)
15
>>> partition(100)
190569292
>>> partition(1_000)
24061467864032622473692149727991
>>> partition(-7)
Traceback (most recent call last):
    ...
IndexError: list index out of range
>>> partition(0)
Traceback (most recent call last):
    ...
IndexError: list assignment index out of range
>>> partition(7.8)
Traceback (most recent call last):
    ...
TypeError: 'float' object cannot be interpreted as an integer

dynamic_programming.integer_partition.n