Ottenere tutti i numeri che si sommano a un numero

Question

Sto cercando di trovare un modo per visualizzare tutti i possibili set di X interi che si sommano a un intero dato. per esempio per ottenere tutti i set di 2 interi che compongono 5 avrei:

1, 4 
2, 3 

O per 3 interi che fanno 6:

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

Ho solo bisogno di numeri interi non compreso 0 e ha solo bisogno di lavorare fino a circa 15 in un set e 30 max. numero.

Non sono nemmeno sicuro se questo ha un termine matematicamente. È simile alla fattorizzazione, immagino?

Answer 1

Ecco un modo per risolvere questo 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 

è possibile utilizzarlo in questo modo.

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

C'è un frammento di 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) 

usare in questo modo:

for p in sum_to_n(4):  
    print p 

Uscite:

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

Answer 4

questi sono chiamati partizioni del numero intero in questione. Altri hanno fornito collegamenti per definirli.

Un trucco per fare queste cose è spesso farlo in modo ricorsivo. Ad esempio, supponiamo di voler formare tutti i modi distinti per creare 10 come somma di esattamente tre numeri interi, nessuno dei quali appare più di una volta.

Guardare il più grande componente possibile di tale somma. Può essere il 10? No, dal momento che se il componente più grande è un 10, allora cosa rimane? Vale a dire 10 - 10 = 0. Si scopre che se l'elemento più grande nella somma è un 7, allora ciò che rimane, per essere partizionato in una somma di due numeri interi positivi è 3. E possiamo rompere 3 in una somma di due interi distinti esattamente in un modo. Quindi {7,2,1} è una tale partizione e l'unica partizione che coinvolge un elemento grande come 7.

Può 6 essere utilizzato come l'elemento più grande? Se è così, allora avremmo 4 rimanenti. E possiamo rompere 4 esattamente in un modo, per ottenere la partizione {6,3,1}. Ulteriore ricerca produrrà altre partizioni di 10 come {5,4,1}, {5,3,2}. Nessun altro può esistere.

Il punto è che questa operazione può essere facilmente definita come funzione ricorsiva. Con un'accurata codifica, si potrebbe persino usare la memoizzazione, per evitare di ricalcolare ciò che abbiamo visto prima.

Answer 5

La tua domanda può essere riformulata così:

Dato un numero N, trovare tutti i set [S1, S2, S3 .....] in cui la somma di ogni set è uguale a N. La dimensione dei set è data dal numero L.

---

Prima prendiamo in considerazione il caso di L=2 .Questo significa che si possono avere i seguenti set

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

chiamerò questa soluzione la base e presto capire perché .

Cambiamo la nostra L per 3 ora e rifare la nostra risposta:

Quindi prendiamo in considerazione il numero 9. Ha esistono un elenco del genere L tale che sum(L) + 9 = 10? La risposta ovvia è No, ma ciò che è interessante qui non è la risposta, ma la domanda stessa. Fondamentalmente stiamo chiedendo un set di elementi 2 che può essere riassunto come il numero 1. Questo è lo stesso problema risolto dalla soluzione di base.

Così dunque per ogni numero x in [9,8,7,6,5,4,3,2,1] si tenta di trovare un set [a,b] tale che x+a+b = 10.

Questa non è una risposta completa, ma l'idea è che si vede il modello qui, e l'uso ricorsione per calcolare il caso base, come fatto in precedenza e quindi capire la chiamata ricorsiva che completerà la vostra soluzione. In bocca al lupo!