Python/dynamic_programming/integer_partition.py at master · FrogBattle/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from __future__ importprint_function

try:
xrange#Python 2
exceptNameError:
xrange=range#Python 3

try:
raw_input#Python 2
exceptNameError:
raw_input=input#Python 3

'''
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.
'''
defpartition(m):
memo= [[0for_inxrange(m)] for_inxrange(m+1)]
foriinxrange(m+1):
memo[i][0] =1

forninxrange(m+1):
forkinxrange(1, m):
memo[n][k] +=memo[n][k-1]
ifn-k>0:
memo[n][k] +=memo[n-k-1][k]

returnmemo[m][m-1]

if__name__=='__main__':
importsys

iflen(sys.argv) ==1:
try:
n=int(raw_input('Enter a number: '))
print(partition(n))
exceptValueError:
print('Please enter a number.')
else:
try:
n=int(sys.argv[1])
print(partition(n))
exceptValueError:
print('Please pass a number.')