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[http://en.wikipedia.org/wiki/Integer_partition].
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 [http://www.site.uottawa.ca/~ivan/F49-int-part.pdf]
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)
    # algorithms for generating integer partitions. See
    # http://www.site.uottawa.ca/~ivan/F49-int-part.pdf for more
    # information. This algorithms 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}
<<categories>>Mathematics