## Integer Partition

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}```

 Category Mathematics