python中如何实现对数字的分解？

Question

例如，把9分解为不超过5个数字的和，且每个数字为正整数，均大于0小于4，如何利用python程序找到所有的分解情况？

Answer 1

注：已修改少于5个数相加的情况。

比较傻的方法，先暴力求所有组合，然后根据Counter统计频次，频次不同的就是不同组合。

In [1]: res_list = []

In [2]: for i in range(0,4):
   ...:     for j in range(0,4):
   ...:         for k in range(0,4):
   ...:             for l in range(0,4):
   ...:                 for m in range(0,4):
   ...:                     if i+j+k+l+m == 9:
   ...:                         res_list.append([i,j,k,l,m])
   ...:

In [3]: from collections import Counter

In [4]: dic = dict()

In [5]: for list in res_list:
   ...:     k = str(Counter(list))
   ...:     if k not in dic:
   ...:         dic[k] = list
   ...:

In [6]: dic.values()
Out[6]: dict_values([[0, 0, 3, 3, 3], [0, 1, 2, 3, 3], [0, 2, 1, 3, 3], [0, 2, 2, 2, 3], [1, 0, 2, 3, 3], [1, 1, 1, 3, 3], [1, 1, 2, 2, 3], [1, 2, 0, 3, 3], [1, 2, 2, 2, 2], [2, 0, 1, 3, 3], [2, 1, 0, 3, 3], [2, 1, 1, 2, 3], [2, 2, 2, 3, 0]])

Answer 2

from itertools import combinations_with_replacement 
#combinations_with_replacement 组合,有重复（有放回抽样组合）
S=[]
U=[1,2,3]
for i in range(6):
    for j in combinations_with_replacement(U,i):
        if sum(j)==9: 
            S.append(j)

Answer 3

组合再按sum过滤的方法的确多做了很多运算，更好的方法是递归做减法

def dfs(rest, pre=1, has=()):
    if rest == 0: yield has
    if rest <= 0: return
    for cur in range(1, 5):
        if cur >= pre:         # 避免重复
            yield from dfs(rest-cur, cur, has+(cur,))

print(list(dfs(9)))

输出

[(1, 1, 1, 1, 1, 1, 1, 1, 1),
 (1, 1, 1, 1, 1, 1, 1, 2),
 (1, 1, 1, 1, 1, 1, 3),
 (1, 1, 1, 1, 1, 2, 2),
 (1, 1, 1, 1, 1, 4),
 (1, 1, 1, 1, 2, 3),
 (1, 1, 1, 2, 2, 2),
 (1, 1, 1, 2, 4),
 (1, 1, 1, 3, 3),
 (1, 1, 2, 2, 3),
 (1, 1, 3, 4),
 (1, 2, 2, 2, 2),
 (1, 2, 2, 4),
 (1, 2, 3, 3),
 (1, 4, 4),
 (2, 2, 2, 3),
 (2, 3, 4),
 (3, 3, 3)]