GS (070901) Cette procédure détermine toutes les partitions d'un nombre entier n. Autrement dit toutes les combinaisons d'entiers positifs inférieurs où égale à n dont la somme vaut n.
Pour ce faire, on utilise l'algorithme de Zoghbi et Stojmenovic issue de l'article Fast Algorithms for Generating Integer Partitions (1994) [1]. Par rapport à l'algorithme naïf, celui-ci tient compte de la distribution statistique des tailles des partitions en traitant à part les cas où il y a une somme de deux nombres.
# --------------------------------------------------------------- # Calcule toutes les partitions d'un entier n et renvoie la liste # # Références: http://www.site.uottawa.ca/~ivan/F49-int-part.pdf # --------------------------------------------------------------- proc ZS1 {n} { set l [string repeat "1 " $n] lset l 0 $n set m [set h 0] lappend zs [lindex $l 0] while {[lindex $l 0] != 1} { if {[lindex $l $h] == 2} then { incr m lset l $h 1 incr h -1 } else { set t [expr {$m - $h + 1}] lset l $h [set r [expr {[lindex $l $h] - 1}]] while {$t >= $r} { lset l [incr h] $r incr t -$r } if {$t == 0} then { set m $h } else { set m [expr {$h + 1}] if {$t > 1} {lset l [incr h] $t} } } lappend zs [lrange $l 0 $m] } return $zs }
Tests:
% foreach p [ZS1 3] {puts $p} 3 2 1 1 1 1 % foreach p [ZS1 5] {puts $p} 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 % foreach p [ZS1 9] {puts $p} 9 8 1 7 2 7 1 1 6 3 6 2 1 6 1 1 1 5 4 5 3 1 5 2 2 5 2 1 1 5 1 1 1 1 4 4 1 4 3 2 4 3 1 1 4 2 2 1 4 2 1 1 1 4 1 1 1 1 1 3 3 3 3 3 2 1 3 3 1 1 1 3 2 2 2 3 2 2 1 1 3 2 1 1 1 1 3 1 1 1 1 1 1 2 2 2 2 1 2 2 2 1 1 1 2 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1