我想生成所有长度为N且总和为S的可能列表。我编写了一些代码来实现这一点,但在处理任何大型数据时(特别是当N=5,S=100时),我遇到了内存溢出错误。
我正在寻找更好的解决方案或改进我的代码以便能够处理N=5,S=100。以下两个程序可以联合创建嵌套列表中的所有可能数字组合,然后重新设计它们以符合正确格式。下面是一些示例输出。
我知道我的代码并不是最好的。我是一名工程师(我知道,我知道),所以编码并不是我的专长。我感谢您提供的任何帮助。
编辑:我只想澄清几件事情。首先,在列表中放置0是可以的,列表中可以包含多个相同的数字,并且列表中数字的顺序很重要。
我正在寻找更好的解决方案或改进我的代码以便能够处理N=5,S=100。以下两个程序可以联合创建嵌套列表中的所有可能数字组合,然后重新设计它们以符合正确格式。下面是一些示例输出。
我知道我的代码并不是最好的。我是一名工程师(我知道,我知道),所以编码并不是我的专长。我感谢您提供的任何帮助。
编辑:我只想澄清几件事情。首先,在列表中放置0是可以的,列表中可以包含多个相同的数字,并且列表中数字的顺序很重要。
def nToSum(N,S):
''' Creates a nested list of all possible lists of length N that sum to S'''
if N <= 1: #base case
return [S]
else:
L = []
for x in range(S+1): #create a sub-list for each possible entry of 0 to S
L += [[x,nToSum(N-1,S-x)]] #create a sub-list for this value recursively
return L
def compress(n=[],L): #designed to take in a list generated by nToSum
'''takes the input from nToSum as list L, and then flattens it so that each list is a
top level list. Leading set n is the "prefix" list, and grows as you climb down the
sublists'''
if type(L[0]) == int: #base case: you have exposed a pure integer
return [n+L] #take that integer, and prepend the leading set n
else:
Q = []
for x in L: # look at every sublist
Q += compress(n+[x[0]],x[1]) # for each sublist, create top level lists recursively
return Q # note: append x[0] to leading set n
>>> nToSum(3,3)
[[0, [[0, [3]], [1, [2]], [2, [1]], [3, [0]]]], [1, [[0, [2]], [1, [1]], [2, [0]]]], [2, [[0, [1]], [1, [0]]]], [3, [[0, [0]]]]]
>>> compress([],nToSum(3,3))
[[0, 0, 3], [0, 1, 2], [0, 2, 1], [0, 3, 0], [1, 0, 2], [1, 1, 1], [1, 2, 0], [2, 0, 1], [2, 1, 0], [3, 0, 0]]