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