在Python中生成所有长度为N的总和为S的所有可能列表 [英] Generate all possible lists of length N that sum to S in Python
问题描述
我正在尝试生成所有可能的长度N总计为S的列表.我已经编写了一些代码来做到这一点，但是对于任何较大的东西(特别是，我希望N = 5，S = 100)，我遇到内存溢出错误.
I'm trying to generate all possible lists of Length N that sum to S. I've written some code to do so, but on anything large (in particular, I want N=5, S=100), I run into memory overflow errors.
我正在寻找一个更好的解决方案，或者一种改进我的代码的方法，以便可以在N = 5，S = 100上运行它.下面的这两个程序协同工作，以在嵌套列表中创建所有可能的数字组合，然后将它们重新加工为正确的格式.下面是一些示例输出.
I'm looking for either a better solution to the problem, or a way to improve my code so I can run it on N=5, S=100. These two programs below work in tandem to create all the possible number combinations in nested lists, and then re-work them to be the right format. Some sample output is reproduced below.
我知道我的代码不是最好的.我是一名行业工程师(我知道，我知道)，所以编码并不是我的专长.感谢您能提供的任何帮助.
I know my code isn't the best. I'm an engineer by trade (I know, I know), so coding isn't exactly my forte. I appreciate any help you can provide.
我只是想澄清一些事情.首先，列表中可以为零，列表可以包含相同数字的倍数，并且列表中数字的顺序很重要.
I just wanted to clarify a few thing. First, it's ok to have zero in the lists, the lists can contain multiples of the same number, and the order of the numbers in the lists matters.
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]]
推荐答案
使用生成器可以节省内存(如果使用Python 2，请使用xrange代替range).这就是我想出的.它与您的nToSum非常相似，而无需compress.
Using a generator saves on memory (usexrange instead of range if using Python 2). This is what I came up with. It is very similar to your nToSum without the need for compress.
def sums(length, total_sum):
if length == 1:
yield (total_sum,)
else:
for value in range(total_sum + 1):
for permutation in sums(length - 1, total_sum - value):
yield (value,) + permutation
L = list(sums(5,100))
print('total permutations:',len(L))
# First and last 10 of list
for i in L[:10] + L[-10:]:
print(i)
输出
total permutations: 4598126
(0, 0, 0, 0, 100)
(0, 0, 0, 1, 99)
(0, 0, 0, 2, 98)
(0, 0, 0, 3, 97)
(0, 0, 0, 4, 96)
(0, 0, 0, 5, 95)
(0, 0, 0, 6, 94)
(0, 0, 0, 7, 93)
(0, 0, 0, 8, 92)
(0, 0, 0, 9, 91)
(98, 0, 2, 0, 0)
(98, 1, 0, 0, 1)
(98, 1, 0, 1, 0)
(98, 1, 1, 0, 0)
(98, 2, 0, 0, 0)
(99, 0, 0, 0, 1)
(99, 0, 0, 1, 0)
(99, 0, 1, 0, 0)
(99, 1, 0, 0, 0)
(100, 0, 0, 0, 0)
这篇关于在Python中生成所有长度为N的总和为S的所有可能列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
