Create all possible lists of length N that sum with S in Python

Question

I am trying to create all possible lists of length N that are summed with S. I wrote code for this, but on any large one (in particular, I want N = 5, S = 100), I have errors in memory overflow.

I'm looking for either the best solution to the problem, or a way to improve my code, so I can run it on N = 5, S = 100. The two programs below work in tandem to create all possible combinations of numbers in nested lists, and then process them into the correct format. The following is an example of some output.

I know that my code is not the best. I am an engineer by profession (I know, I know), so coding is not really my strong point. I appreciate any help you can provide.

EDIT: I just wanted to clarify something. Firstly, it’s normal to have zero in lists, lists can contain the multiplicity of the same number, and the order of 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 SL += [[x,nToSum(N-1,Sx)]] #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]] 

Answer 1

Using a generator saves memory (use xrange instead of range when using Python 2). This is what I came up with. This 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) 

Exit

 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) 

Answer 2

The above solution seems good, but the "sums" should be replaced with "f" in the code.