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