Keith Vetter 2011-04-01 : In number theory, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers[L1 ]. I recently needed to to partition a number for some recreational programming.
There's probably code somewhere on this wiki which does this already, but I couldn't find it so I thought add mine.
The definitive algorithms for partition are by Zoghbi and Stojmenovic [L2 ] and they have a constant average delay, i.e. the amount of effort to produce the next result is constant. Below is a Tcl implementation of their ZS1 algorithm which produces the result in anti-lexical order.
proc ZS1 {n} {
# This module implements the Zoghbi and Stojmenovic ZS1 (not ZS2)
# algorithm for generating integer partitions. See
# http://www.site.uottawa.ca/~ivan/F49-int-part.pdf for more
# information. This algorithm has been proven to have constant
# average delay, that is, the amount of effort it takes to produce
# the next result in the series.
set all {}
for {set i 1} {$i <= $n} {incr i} { set X($i) 1 }
set X(1) $n
set m 1
set h 1
lappend all $X(1)
while {$X(1) != 1} {
if {$X($h) == 2} {
incr m
set X($h) 1
incr h -1
} else {
set r [expr {$X($h) - 1}]
set t [expr {$m - $h + 1}]
set X($h) $r
while {$t >= $r} {
incr h
set X($h) $r
set t [expr {$t - $r}]
}
if {$t == 0} {
set m $h
} else {
set m [expr {$h+1}]
if {$t > 1} {
incr h
set X($h) $t
}
}
}
set this {}
for {set i 1} {$i <= $m} {incr i} { lappend this $X($i) }
lappend all $this
}
return $all
} Example:
% ZS1 3
3 {2 1} {1 1 1}
% ZS1 5
5 {4 1} {3 2} {3 1 1} {2 2 1} {2 1 1 1} {1 1 1 1 1}