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