Partitions d'un nombre entier

 

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

Catégorie Mathématiques