python - resueltos - suma de n numeros en c con while

Genera todas las listas posibles de longitud N que suman a S en Python

Question

Intento generar todas las listas posibles de Length N que suman S. He escrito un código para hacerlo, pero en cualquier cosa grande (en particular, quiero N = 5, S = 100), me encuentro con la memoria errores de desbordamiento

Estoy buscando una mejor solución al problema, o una forma de mejorar mi código para poder ejecutarlo en N = 5, S = 100. Estos dos programas a continuación trabajan en conjunto para crear todas las combinaciones de números posibles en listas anidadas, y luego volver a trabajarlas para que tengan el formato correcto. Algunos ejemplos de salida se reproducen a continuación.

Sé que mi código no es el mejor. Soy un ingeniero de oficio (lo sé, lo sé), así que codificar no es exactamente mi fuerte. Agradezco cualquier ayuda que pueda brindar.

EDITAR: Solo quería aclarar algunas cosas. Primero, está bien tener cero en las listas, las listas pueden contener múltiplos del mismo número, y el orden de los números en las listas es importante.

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]]

Answer 1

Usar un generador ahorra memoria, y xrange lugar de range (en Python 2.X, de todos modos), esto es lo que se me ocurrió. Es muy similar a su nToSum sin necesidad de compress .

def f(n,s):
    if n == 1:
        yield (s,)
    else:
        for i in xrange(s + 1):
            for j in f(n - 1,s - i):
                yield (i,) + j

L = list(f(5,100))
print ''total permutations:'',len(L)

# First and last 10 of list
for i in L[:10] + L[-10:]:
    print i

Salida

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)