Obtenga todos los números que se suman a un número

Question

Estoy tratando de encontrar una manera de mostrar todos los conjuntos posibles de enteros X que se suman a un número entero dado. por ejemplo, para obtener todos los conjuntos de 2 enteros que hacen 5 Tendría:

1, 4 
2, 3 

O durante 3 enteros que hacen 6:

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

necesito solamente números enteros no incluyendo 0 y sólo necesita trabajar en hasta alrededor de 15 en un conjunto y 30 máx. número.

Ni siquiera estoy seguro de si esto tiene un término matemáticamente. Es similar a la factorización, supongo?

Answer 1

Aquí es 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 

Usted puede utilizar de esta manera.

for partition in sum_to_n(6, 3): 
    print partition 

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

Answer 2

http://en.wikipedia.org/wiki/Partition_(number_theory)

http://mathworld.wolfram.com/Partition.html

http://code.activestate.com/recipes/218332/

Answer 3

Hay un fragmento here:

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) 

utilizar de esta manera:

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] 

Answer 4

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

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

Mire el componente más grande posible en esa suma. ¿Puede ser 10? No, ya que si el componente más grande es un 10, entonces ¿qué queda? Es decir, 10 - 10 = 0. Resulta que si el elemento más grande en la suma es un 7, entonces lo que queda por dividir en una suma de dos enteros positivos es 3. Y podemos dividir 3 en una suma de dos enteros distintos en exactamente una forma. Entonces {7,2,1} es una partición así, y la única partición que involucra un elemento tan grande como 7.

¿Se puede usar 6 como el elemento más grande? Si es así, entonces tendríamos 4 restantes. Y podemos dividir 4 de exactamente una forma, para obtener la partición {6,3,1}. La búsqueda adicional arrojará otras particiones de 10 como {5,4,1}, {5,3,2}. Ningunos otros pueden existir.

El punto es que esta operación se puede definir fácilmente como una función recursiva. Con una codificación cuidadosa, incluso se podría usar la memorización para evitar volver a calcular lo que hemos visto antes.

Answer 5

Su pregunta puede reformularse así:

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

---

En primer lugar vamos a considerar el caso de L=2 .Esta significa que usted puede tener los siguientes conjuntos

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

Voy a llamar a esta solución de la base y pronto ver por qué .

Vamos a cambiar nuestra L a 3 ahora y rehacer nuestra respuesta:

Así que vamos a considerar el número 9. ¿Existe una lista de este tipo L tal que sum(L) + 9 = 10? La respuesta obvia es No, pero lo interesante aquí no es la respuesta, sino la pregunta en sí misma. Básicamente estamos pidiendo un conjunto de elementos 2 que se pueden resumir en el número 1. Este es el mismo problema que fue resuelto por la solución base.

Así que, por tanto, para cada número x en [9,8,7,6,5,4,3,2,1] se 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 descubra la llamada recursiva que completará su solución. ¡Buena suerte!