Obtener todos los números que se sumn a un número

Estoy tratando de encontrar una manera de mostrar todos los conjuntos posibles de enteros X que se sumn a un entero dado. por ejemplo, para obtener los 2 conjuntos de enteros que forman 5 tendría:

1, 4 2, 3 

O para 3 enteros que forman 6:

 1, 1, 4 1, 2, 3 2, 2, 2 

Solo necesito números enteros sin incluir 0 y solo necesita trabajar hasta 15 en un conjunto y 30 como máximo. número.

Ni siquiera estoy seguro de si esto tiene un término matemáticamente. Supongo que es similar a la factorización.

Aquí hay una manera de resolver este problema:

 def sum_to_n(n, size, limit=None): """Produce all lists of `size` positive integers in decreasing order that add up to `n`.""" if size == 1: yield [n] return if limit is None: limit = n start = (n + size - 1) // size stop = min(limit, n - size + 1) + 1 for i in range(start, stop): for tail in sum_to_n(n - i, size - 1, i): yield [i] + tail 

Puedes usarlo así.

 for partition in sum_to_n(6, 3): print partition [2, 2, 2] [3, 2, 1] [4, 1, 1] 

Aquí hay un fragmento:

 from itertools import combinations, chain def sum_to_n(n): 'Generate the series of +ve integer lists which sum to a +ve integer, n.' from operator import sub b, mid, e = [0], list(range(1, n)), [n] splits = (d for i in range(n) for d in combinations(mid, i)) return (list(map(sub, chain(s, e), chain(b, s))) for s in splits) 

Úsalo así:

 for p in sum_to_n(4): print p 

Salidas:

 [4]
 [1, 3]
 [2, 2]
 [3, 1]
 [1, 1, 2]
 [1, 2, 1]
 [2, 1, 1]
 [1, 1, 1, 1]

Estas se llaman particiones del entero en cuestión. Otros han proporcionado enlaces para definirlos.

Un truco para hacer estas cosas es a menudo hacerlas recursivamente. Por ejemplo, supongamos que quisiera formar todas las formas distintas de construir 10 como la sum de exactamente tres enteros, ninguno de los cuales aparece más de una vez.

Mira el componente más grande posible en esa sum. ¿Puede ser 10? No, ya que si el componente más grande es un 10, ¿qué queda? Es decir, 10 – 10 = 0. Resulta que si el elemento más grande en la sum es un 7, lo que queda, para ser dividido en una sum de dos enteros positivos es 3. Y podemos dividir 3 en una sum de dos enteros distintos de una manera exacta. Entonces {7,2,1} es una partición de este tipo, y la única partición que involucra un elemento tan grande como 7.

¿Se puede usar el 6 como el elemento más grande? Si es así, entonces tendríamos 4 restantes. Y podemos romper 4 de una manera exacta, para obtener la partición {6,3,1}. La búsqueda adicional producirá otras particiones de 10 como {5,4,1}, {5,3,2}. Ningún otro puede existir.

El punto es que esta operación puede definirse fácilmente como una función recursiva. Con una encoding cuidadosa, incluso se puede utilizar la memoria, para evitar volver a calcular lo que hemos visto antes.

Tu pregunta se puede reformular así:

Dado un número N, encuentre todos los conjuntos [S1, S2, S3 …..] donde la sum de cada conjunto sea igual a N. El tamaño de los conjuntos viene dado por el número L.


Primero, consideremos el caso de L=2 Esto significa que puedes tener los siguientes conjuntos

(9,1) , (8,2), (7,3) , (6,4) , (5,5)

Llamaré a esto la solución base y pronto verás por qué.

Cambiemos nuestra L a 3 ahora y rehacamos nuestra respuesta:

Entonces, consideremos el número 9. ¿Existe tal lista L que sum(L) + 9 = 10 ? La respuesta obvia es No, pero lo que es interesante aquí no es la respuesta sino la pregunta en sí misma. Básicamente estamos pidiendo un conjunto de 2 elementos que pueden resumirse para ser el número 1 . Este es el mismo problema que se resolvió con la solución base.

Por lo tanto, para cada número x en [9,8,7,6,5,4,3,2,1] intenta encontrar un conjunto [a,b] tal que x+a+b = 10 .

Esta no es una respuesta completa, pero la idea es que vea el patrón aquí y use la recursión para calcular el caso base como se hizo anteriormente y luego determine la llamada recursiva que completará su solución. ¡Buena suerte!