import copy
M=4; N=9; p=list(); pm=list(range(M)); def partition(index): global p,pm if index==M: if sum(pm)==N: pmp=copy.deepcopy(pm) pmp.sort() if not pmp in p: p.append(pmp) else: for val in range(N+1): pm[index]=val partition(index+1) def partition2(index,begins): global p2,pm; if index==M-1: pm[index]=N-sum(pm[0:len(pm)-1]) if pm[index]>=pm[index-1]: print(pm) else: ends=sum(pm[0:index])+begins ends=N-ends+1 for val in range(begins,ends): pm[index]=val; partition2(index+1,val) if __name__ == '__main__': partition(0) for pv in p: print(pv) print(10*'#') partition2(0,0) 结果： [0, 0, 0, 9] [0, 0, 1, 8] [0, 0, 2, 7] [0, 0, 3, 6] [0, 0, 4, 5] [0, 1, 1, 7] [0, 1, 2, 6] [0, 1, 3, 5] [0, 1, 4, 4] [0, 2, 2, 5] [0, 2, 3, 4] [0, 3, 3, 3] [1, 1, 1, 6] [1, 1, 2, 5] [1, 1, 3, 4] [1, 2, 2, 4] [1, 2, 3, 3] [2, 2, 2, 3] 相比而言，方法partion2更可取，partion仅仅是采用穷举的方法验证partion2方法是正确的。 写程序的时候出现了一点点意外，白partion写成如下形式(红色部分)： def partition(index): global p,pm if index==M: if sum(pm)==N: pm.sort() pmp=copy.deepcopy(pm) if not pmp in p: p.append(pmp) else: for val in range(N+1): pm[index]=val partition(index+1) 结果输出如下： [0, 0, 0, 9] [0, 0, 1, 8] [0, 0, 2, 7] [0, 0, 3, 6] [0, 0, 4, 5]
