# Essays/AllPartitions

# All Partitions

A partition of n is a list of positive integers whose sum is n.

## 1. Iterative Algorithm

The following is an improvement of programs by R.E. Boss [Vector, Vol. 23 No. 4, September 2008] and Roger Hui [Jwiki, 2008 12 8]:

AllPartitions =: ;@AllParts EACH =: &.> AllParts =: Ns ,.EACH Parts Ns =: >:@i. Parts =: Build^:N Start Start =: <@,:@i.@0: N =: <:@[ >. 0: Build =: <@;@Next , ] Next =: (Max #) Ps ] Max =: - <. ] Ps =: Ns@[ Join EACH {. Join =: [ ,. Select # ] Select =: >: {."1

`AllPartitions (n)` produces a table of all partitions of `n` in ascending order with non-ascending parts, padded with zeros.
For example:

AllPartitions 6 1 1 1 1 1 1 2 1 1 1 1 0 2 2 1 1 0 0 2 2 2 0 0 0 3 1 1 1 0 0 3 2 1 0 0 0 3 3 0 0 0 0 4 1 1 0 0 0 4 2 0 0 0 0 5 1 0 0 0 0 6 0 0 0 0 0

`AllPartitions 10` is a 42 by 10 table of all partitions of 10. Inspect how it works:

`AllParts 10` contains integers 1 to 10 stitched respectively onto ten tables in boxes built iteratively by `Parts 10` starting with a boxed empty table, as seen by executing:

10 Build^:9 Start 10

Halfway through, `parts5 =. 10 Build^:5 Start 10` is all partitions of 5,4,3,2,1,0 in six boxes. The next box comes from `10 Next parts5` (see below) razed to a table and boxed to become the first box of `parts6 =. 10 Build^:6 Start 10`. Similarly, notice progressively fewer boxes in `10 Next parts6`, etc.

To see how `10 Next parts5` works, first compute the maximum leading part. For example: `10 Max #parts5` is 4 and `10 Max #parts6` is 3, etc.

Then study `Ps`: Join each integer from 1 to the max onto the first max boxes, respectively, as in `1 2 3 4 Join EACH 4 {. parts5` and `1 2 3 Join EACH 3 {. parts6`.

Finally, `Join`: Stitch the left integer onto selected items of the right (opened) table where the integer is >: the leading part. Inside the second box is `p =. > 1 { parts5`.
`2 Select p` is `1 1 1 0 0`, so `2 Join p` is the second box of `10 Next parts5`. Other boxes similarly.

Now count the number of all partitions for each of twenty integers:

#@AllPartitions"0 i.20 0 1 2 3 5 7 11 15 22 30 42 56 77 101 135 176 231 385 490

All partitions of n must sum to n:

Test =: +/"1 *./ . = {:@$ *./ Test@AllPartitions"0 i.20 1

Plot time and space:

Time =: 6!:2 Space =: 7!:2 load 'plot' plot n ; Time"1 'AllPartitions ' ,"1 ":,.n=.i.61 plot n ; Space"1 'AllPartitions ' ,"1 ":,.n=.i.61

Also see Essays/Partitions (on general partitioning) and "All Integer Partitions" (for an exhaustive break-down of these kinds of partitions).

Contributed by Howard Peelle

## 2. Co-recursive Algorithm

This algorithm computes all partitions of n with exactly k parts by adding 1 recursively to all partitions of (n-k) with k parts.

AP =: ;@AllParts AllParts =: <@Parts"0 >:@i. ELSE =: ` WHEN =: @. Parts =: Add1 ELSE Ones WHEN <: Ones =: < }. ] ,:@# 1: Add1 =: 1: + - AP ]

`AP (n)` produces all partitions of `n` in *descending* order by groups of increasing lengths of non-ascending parts padded with zeros.
For example, `AP 10` is a 42 by 10 table of all partitions of 10. `AllParts 10` produces ten boxed tables of partitions with 1 part, 2 parts, 3 parts, etc.

Note that `AP` is ambivalent. So `10 AP 3` razes boxes of the following:

10 Parts 1 10 10 Parts 2 9 1 8 2 7 3 6 4 5 5 10 Parts 3 8 1 1 7 2 1 6 3 1 5 4 1 6 2 2 5 3 2 4 4 2 4 3 3

To speed up the program, include an early exit when n or k=1:

AP =: ;@AllParts ELSE N WHEN (1:e.,) N =: ,:@{.~

See how `Parts` works co-recursively with `AP`:

`10 Parts 3` becomes `1 + 7 AP 3` then `1 + (7 Parts 1),(7 Parts 2),(7 Parts 3)`

`7 Parts 1` becomes `1 + 6 AP 1` then `1 + 6 N 1` then `7`

`7 Parts 2` becomes `1 + 5 AP 2` then `1 + (5 Parts 1),(5 Parts 2)`

`5 Parts 1` becomes `5`

`5 Parts 2` becomes `1 + 3 AP 2` then `1 + (3 Parts 1),(3 Parts 2)`

`3 Parts 1` becomes `3`

`3 Parts 2` becomes `1 + 1 AP 2` then `1 + 1 N 2` then `1 + 1 0`

`7 Parts 3` becomes `1 + 4 AP 3` then `1 + (4 Parts 1),(4 Parts 2),(4 Parts 3)`

`4 Parts 1` becomes `4`

`4 Parts 2` becomes `1 + 2 AP 2` then `1 + (2 Parts 1),(2 Parts 2)`

`2 Parts 1` becomes `2`

`2 Parts 2` becomes `2 Ones 2` then `1 1`

`4 Parts 3` becomes `1 + 1 AP 3` then `1 + 1 N 3` then `1 + 1 0 0`

After recursion reaches its depths, reconstruct the results:

4 Parts 3 2 1 1 4 Parts 2 3 1 2 2 4 Parts 1 4 4 AP 3 4 0 0 3 1 0 2 2 0 2 1 1 7 Parts 3 5 1 1 4 2 1 3 3 1 3 2 2 3 Parts 2 2 1 3 Parts 1 3 3 AP 2 3 0 2 1 5 Parts 2 4 1 3 2 5 Parts 1 5 5 AP 2 5 0 4 1 3 2 7 Parts 2 6 1 5 2 4 3 7 Parts 1 7

Assemble `(7 Parts 1),(7 Parts 2),(7 Parts 3)` to get:

7 AP 3 7 0 0 6 1 0 5 2 0 4 3 0 5 1 1 4 2 1 3 3 1 3 2 2

Finally, add 1 to get:

10 Parts 3 8 1 1 7 2 1 6 3 1 5 4 1 6 2 2 5 3 2 4 4 2 4 3 3

Compute other `10 Parts (n)` similarly and count the numbers of these exact partitions:

(#@Parts"0 Ns) 10 1 5 8 9 7 5 3 2 1 1

Sum is the number of all partitions:

#AP 10 42

Speed up the program for large n:

AP =: ;@AllParts Parts =: Add1`Ones@.<:`N@.(]=1:) N =: ,.@[

Use Fix and Memo for further speed-ups: `AP =: AP f. M.`

Plot time and space:

Time =: 6!:2 Space =: 7!:2 load 'plot' plot n ; Time"1 'AP ' ,"1 ":,.n=.i.61 plot n ; Space"1 'AP ' ,"1 ":,.n=.i.61

Compare this performance to section 1 above.

Contributed by Howard Peelle