Advertisement
Radeen10-_

Integer Partition

Feb 12th, 2022
1,184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.33 KB | None | 0 0
  1. 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. If order matters, the sum becomes a composition. For example, 4 can be partitioned in five distinct ways:
  2.     4
  3. 3 + 1
  4. 2 + 2
  5. 2 + 1 + 1
  6. 1 + 1 + 1 + 1
  7. exp_sum(1) # 1
  8. exp_sum(2) # 2  -> 1+1 , 2
  9. exp_sum(3) # 3 -> 1+1+1, 1+2, 3
  10. exp_sum(4) # 5 -> 1+1+1+1, 1+1+2, 1+3, 2+2, 4
  11. exp_sum(5) # 7 -> 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 5, 2+3
  12.  
  13. exp_sum(10) # 42
  14. exp_sum(50) # 204226
  15. exp_sum(80) # 15796476
  16. exp_sum(100) # 190569292
  17. =====================================================================================================================================
  18. @solution:
  19.    
  20. import operator
  21. get_last_item = operator.itemgetter(-1)
  22. def exp_sum(n):
  23.     p_matrix=[[0]*(n+1) for x in range(n+1)]
  24.     # return p_matrix
  25.     for i in range(0,n+1):
  26.         p_matrix[i][0]=1
  27.     for i in range(1,n+1):
  28.         for j in range(1,n+1):
  29.             if i>j:
  30.                 p_matrix[i][j]=p_matrix[i-1][j]
  31.             else:
  32.                 exclude_i=p_matrix[i-1][j]
  33.                 include_i=p_matrix[i][j-i]
  34.                 p_matrix[i][j]=exclude_i+include_i
  35.     return p_matrix[n][-1]
  36.  
  37.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement