python - sumatoria - Obtener todos los números que se suman a un número

sumar los numeros del 1 al 100 python

Question

Estoy tratando de encontrar una manera de mostrar todos los conjuntos posibles de enteros X que se suman 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.

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

Answer 2

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]

Answer 3

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 suma de exactamente tres enteros, ninguno de los cuales aparece más de una vez.

Mira el componente más grande posible en esa suma. ¿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 suma es un 7, lo que queda, para ser dividido en una suma de dos enteros positivos es 3. Y podemos dividir 3 en una suma 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 dará como resultado otras particiones de 10 como {5,4,1}, {5,3,2}. Ningún otro puede 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 puede utilizar la memoria, para evitar volver a calcular lo que hemos visto antes.

Answer 4

Tu pregunta se puede reformular así:

Dado un número N, encuentre todos los conjuntos [S1, S2, S3 .....] donde la suma 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 interesante aquí no es la respuesta sino la pregunta en sí. Básicamente estamos pidiendo un conjunto de 2 elementos que se pueden resumir como el número 1 . Este es el mismo problema que fue resuelto por 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 descubra la llamada recursiva que completará su solución. ¡Buena suerte!