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[1 ]. 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 [2 ] 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}