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

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
N =: ,.@[

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

Plot time and space:

Time  =: 6!:2
Space =: 7!:2