In particolare, la cosa che vorrei far notare è che esiste una formula abbastanza chiusa (o comunque non troppo aperta) per calcolare la cosa che chiede jumoonp, che si ricava nel seguente modo.
Supponiamo di voler scrivere [latex]s[/latex] come somma di [latex]n[/latex] numeri, ciascuno dei quali compreso fra 0 e [latex]m[/latex]. È facile convincersi che il numero di combinazioni è il coefficiente di grado [latex]s[/latex] del polinomio [latex](1+x+x^2+\ldots+x^m)^n[/latex]. Ma [latex]1+x+x^2+\ldots+x^m=\frac{1-x^{m+1}}{1-x}[/latex], quindi [latex](1+x+x^2+\ldots+x^m)^n=\frac{(1-x^{m+1})^n}{(1-x)^n}[/latex]. Il numeratore si sviluppa con Newton: [latex](1-x^{m+1})^n=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}x^{i(m+1)}[/latex]; il denominatore con Taylor: [latex](1-x)^{-n}=\sum_{i=0}^{+\infty}\binom{n+i-1}{n-1}x^i[/latex]. Dunque troviamo che [latex](1+x+x^2+\ldots+x^m)^n=\left(\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}x^{i(m+1)}\right)\left(\sum_{i=0}^{+\infty}\binom{n+i-1}{n-1}x^i\right)[/latex], da cui il coefficiente di grado [latex]s[/latex] del polinomio (ovvero il numero che andiamo cercando) è [latex]\sum_{i=0}^{\left\lfloor\frac{s}{m+1}\right\rfloor}(-1)^i\binom{n}{i}\binom{n+s-i(m+1)-1}{n-1}[/latex].
Poi, già che ci sono e non ho nulla da fare, proviamo a dare una dimostrazione del perchè i controlli sul minimo e sul massimo sono sufficienti (mi rifaccio al codice di Breston).
Nel momento di stampare la combinazione, la funzione viene chiamata con il parametro p = 1; pertanto avremo m = S - 0 * t - partialsum = S - partial sum; inoltre (saltando per ora i controlli) anche M = S - partialsum = m. Quindi il ciclo for viene eseguito una sola volta con i = S - partialsum; essendo partialsum la somma di tutti i numeri già presenti nella combinazione, la somma di tutti i numeri finora presenti più i vale esattamente partialsum + i = S, come desiderato. L'unico problema potrebbe sorgere quando S - partialsum è troppo grande (> t) o troppo piccolo (< 0), ma in questo caso si vede facilmente che arriviamo ad avere M < m, quindi il ciclo non viene eseguito, come desiderato.
E, per concludere, uno script in Haskell che trova effettivamente tutte le combinazioni in modo non troppo efficiente ma sicuramente elegante:
Codice: Seleziona tutto
findCombinations n s m
| n == 1 = if 0 <= s && s <= m then [[s]] else []
| otherwise = concatMap (\x -> map (x :) $ findCombinations (n - 1) (s - x) m) [0 .. m]
