GeezerVison is showing github.com — Python/dynamic_programming/integer_partition.py at python3.15t · TheAlgorithms/Python

Expand file tree

integer_partition.py

Copy path

More file actions

Latest commit

History

61 lines (54 loc) · 1.72 KB

integer_partition.py

Copy path

File metadata and controls

61 lines (54 loc) · 1.72 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

"""

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)

"""

def partition(m: int) -> int:

"""

>>> partition(5)

>>> partition(7)

>>> 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

"""

memo: list[list[int]] = [[0 for _ in range(m)] for _ in range(m + 1)]

for i in range(m + 1):

memo[i][0] = 1

for n in range(m + 1):

for k in range(1, m):

memo[n][k] += memo[n][k - 1]

if n - k > 0:

memo[n][k] += memo[n - k - 1][k]

return memo[m][m - 1]

if __name__ == "__main__":

import sys

if len(sys.argv) == 1:

try:

n = int(input("Enter a number: ").strip())

print(partition(n))

except ValueError:

print("Please enter a number.")

else:

try:

n = int(sys.argv[1])

print(partition(n))

except ValueError:

print("Please pass a number.")