Calcolo delle somme possibili dato un risultato conosciuto
ciao a tutti ,
è il mio primo post su questo forum , e sono qui per cercare un aiuto ad un problema che mi sta letteralmente consumando .
vengo al dunque:
avrei bisogno di trovare, conoscendo il risultato ed il numero di addendi, tutte le combinazioni di somme possibili .
Quindi dovrei trovare un algoritmo in grado di crearmi le combinazioni lineari di vettori
come riferimento posso dire che :
A) l'ordine degli addendi non è importante.
B) le somme , poste in ordine diverso, non devono ripetersi (ma se anche fosse sarebbe già un buon risultato).
quindi, come esmpio, date queste variabili:
risultato = r = 7
addendi = n = 3
vorrei che venissero fuori queste combinazioni:
5+1+1
4+2+1
3+3+1
3+2+2
come primo passo ho scoperto che il numero del primo addendo della prima combinazione è = r-n+1 (non che ci volesse molto)
spero di essermi spiegato chiaramente.
un grazie a chi risciurà anche solametente ad indirizzarmi verso la strada giusta.
è il mio primo post su questo forum , e sono qui per cercare un aiuto ad un problema che mi sta letteralmente consumando .
vengo al dunque:
avrei bisogno di trovare, conoscendo il risultato ed il numero di addendi, tutte le combinazioni di somme possibili .
Quindi dovrei trovare un algoritmo in grado di crearmi le combinazioni lineari di vettori
come riferimento posso dire che :
A) l'ordine degli addendi non è importante.
B) le somme , poste in ordine diverso, non devono ripetersi (ma se anche fosse sarebbe già un buon risultato).
quindi, come esmpio, date queste variabili:
risultato = r = 7
addendi = n = 3
vorrei che venissero fuori queste combinazioni:
5+1+1
4+2+1
3+3+1
3+2+2
come primo passo ho scoperto che il numero del primo addendo della prima combinazione è = r-n+1 (non che ci volesse molto)
spero di essermi spiegato chiaramente.
un grazie a chi risciurà anche solametente ad indirizzarmi verso la strada giusta.
Risposte
Mmmh..spero di aver capito il problema..se le cifre si possono ripetere(cioè consideri 1+1+5 e 5+1+1 distinte) e sono interi positivi gli addendi allora ho la soluzione, altrimenti. 
......se così fosse allora fai così: facciamo un disegno formati da r+n-1 righette del tipo questa:_
_ _ _ _ _...._ _ Lo rappresento schematicamente così..
Ora..tra questa puoi scegliere r-1 righette da trasformare da così _ a così -. Il disegno divevta quindi una roba del tipo _ _ - _ _ _ ... _ - _. Questa trasformazione ti divide la figura di partenza in n segmenti. Ora crei una funzione f che ad ogni segmento associ un numero in modo che un segmento contenente x trattini sia il numero x.(per esempio,f( _ _ _) =3). Ora, la somma di tutte le r funzioni da come valore n per ogni possibile posizionamento dei -, inoltre per ogni r-upla di interi $z_i$ non negativi tali che $\sum_{i=1}^{r}{z_i}=n$ esiste una e una sola possibile posizione degli - in modo che la somma dei vari f(roba) sia n, a meno di permutazioni (sfortunatamente!!!). Quindi il problema si riduce al contare tutte le possibili posizioni in cui mettere gli - , che, come saprai, si fa con i binomiali..(che non so fare in latex...)
NB: se gli addendi sono strettamente positivi allora si può rimettere a posto con un trucchetto...lascio a te scoprirlo...
scusa se sono poco chiaro ma devo andare e non ho tempo..
......se così fosse allora fai così: facciamo un disegno formati da r+n-1 righette del tipo questa:__ _ _ _ _...._ _ Lo rappresento schematicamente così..
Ora..tra questa puoi scegliere r-1 righette da trasformare da così _ a così -. Il disegno divevta quindi una roba del tipo _ _ - _ _ _ ... _ - _. Questa trasformazione ti divide la figura di partenza in n segmenti. Ora crei una funzione f che ad ogni segmento associ un numero in modo che un segmento contenente x trattini sia il numero x.(per esempio,f( _ _ _) =3). Ora, la somma di tutte le r funzioni da come valore n per ogni possibile posizionamento dei -, inoltre per ogni r-upla di interi $z_i$ non negativi tali che $\sum_{i=1}^{r}{z_i}=n$ esiste una e una sola possibile posizione degli - in modo che la somma dei vari f(roba) sia n, a meno di permutazioni (sfortunatamente!!!). Quindi il problema si riduce al contare tutte le possibili posizioni in cui mettere gli - , che, come saprai, si fa con i binomiali..(che non so fare in latex...)
NB: se gli addendi sono strettamente positivi allora si può rimettere a posto con un trucchetto...lascio a te scoprirlo...
scusa se sono poco chiaro ma devo andare e non ho tempo..
ti ringrazio per il passaggio, ho risolto il problema consultando il libro "Combinatorial algorithms" di Kreher e Stinson , al capitolo 3 c'e' la spiegazione di quello che stavo cercando.
Bene, ti andrebbe di postare tutta la dimostrazione?... 
..
..
beh, butto lì:
trovi tutte le permutazioni di (n-1) elementi dove n è il numero di addendi, permutazioni in cui usi i numeri minori della somma.
A questo punto trovi l ultimo numero n-esimo necessario a raggiungere la somma, se questo è possibile tieni la combinazione altrimenti (se è troppo piccola o sfora) la butti via.
trovi tutte le permutazioni di (n-1) elementi dove n è il numero di addendi, permutazioni in cui usi i numeri minori della somma.
A questo punto trovi l ultimo numero n-esimo necessario a raggiungere la somma, se questo è possibile tieni la combinazione altrimenti (se è troppo piccola o sfora) la butti via.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo