A partition of n is a sorted list x of positive integers such that n=+/x . For example, the following is the sorted list of all the partitions of 5:

┌─┬───┬───┬─────┬─────┬───────┬─────────┐
│5│4 1│3 2│3 1 1│2 2 1│2 1 1 1│1 1 1 1 1│
└─┴───┴───┴─────┴─────┴───────┴─────────┘

All Partitions

We wish to generate the sorted list of all partitions of n .The following is a modified version of a function by R.E. Boss posted to the J Forum on 2005-07-21:

part =: 3 : 'final (, new)^:y <<i.1 0'
new  =: (-i.)@# <@:(cat&.>) ]
cat  =: [ ;@:(,.&.>) -@(<.#) {. ]
final=: ; @: (<@-.&0"1&.>) @ > @ {:

The function maintains a list of the partitions of 0, 1, 2, ... , n grouped by the leading part. The partitions of n are constructed from the partitions of k<n , using the fact that partitions of n that begin with k are all the partitions of n-k that begin with k or less.

The following example demonstrates the process for n=6 :

   ] x=: (,new)^:5 <<i.1 0
┌──┬───┬───────┬─────────────┬─────────────────────┬───────────────────────────────┐
│┌┐│┌─┐│┌─┬───┐│┌─┬───┬─────┐│┌─┬───┬─────┬───────┐│┌─┬───┬─────┬───────┬─────────┐│
│││││1│││2│1 1│││3│2 1│1 1 1│││4│3 1│2 2 0│1 1 1 1│││5│4 1│3 2 0│2 2 1 0│1 1 1 1 1││
│└┘│└─┘│└─┴───┘│└─┴───┴─────┘││ │   │2 1 1│       │││ │   │3 1 1│2 1 1 1│         ││
│  │   │       │             │└─┴───┴─────┴───────┘│└─┴───┴─────┴───────┴─────────┘│
└──┴───┴───────┴─────────────┴─────────────────────┴───────────────────────────────┘

   6 cat >0{x
6
   5 cat >1{x
5 1
   4 cat >2{x
4 2 0
4 1 1
   3 cat >3{x
3 3 0 0
3 2 1 0
3 1 1 1
   2 cat >4{x
2 2 2 0 0
2 2 1 1 0
2 1 1 1 1
   1 cat >5{x
1 1 1 1 1 1

   6 5 4 3 2 1 cat&.> x
┌─┬───┬─────┬───────┬─────────┬───────────┐
│6│5 1│4 2 0│3 3 0 0│2 2 2 0 0│1 1 1 1 1 1│
│ │   │4 1 1│3 2 1 0│2 2 1 1 0│           │
│ │   │     │3 1 1 1│2 1 1 1 1│           │
└─┴───┴─────┴───────┴─────────┴───────────┘
   new x
┌───────────────────────────────────────────┐
│┌─┬───┬─────┬───────┬─────────┬───────────┐│
││6│5 1│4 2 0│3 3 0 0│2 2 2 0 0│1 1 1 1 1 1││
││ │   │4 1 1│3 2 1 0│2 2 1 1 0│           ││
││ │   │     │3 1 1 1│2 1 1 1 1│           ││
│└─┴───┴─────┴───────┴─────────┴───────────┘│
└───────────────────────────────────────────┘

partcheck has the same argument and result as part , but incorporates checks:

partcheck=: 3 : 0
 p=. part y
 assert. 1 = #$p
 assert. 1 = #@$&>p
 assert. y = +/&>p
 assert. p -: ~.p
 assert. p -: \:~p
 assert. p -: \:~&.>p
 assert. (;p) e. i.1+y
 assert. ({.p) -: <y-.0
 assert. ({:p) -: <y$1
)

The Number of Partitions

The number of partitions can be computed using a recurrence equation due to Euler:

$P(n)=\sum _{k=1}^{n}(-1)^{k+1}\left(P(n-{1 \over 2}k(3k-1))+P(n-{1 \over 2}k(3k+1))\right)$

and checked using an asymptotic formula by Hardy and Ramanujan:

$P(n)\sim {1 \over {n\,4{\sqrt {3}}}}\exp {\pi {\sqrt {2n/3}}}$

pnv=: 3 : 0
 k=. 1+i.>.%:y*2%3
 m=. <. y-(-:k)*"1 ]_1 1+/3*k
 v=. ,1x
 for_i. i.-y do. v=. v, -/+/(_1>.m-i){v,0 end.
)

pa=: %@((4*%:3)&*) * ^@o.@%:@((2%3)&*)


   pnv 10
1 1 2 3 5 7 11 15 22 30 42

   {: pnv 4000
1024150064776551375119256307915896842122498030313150910234889093895
   0j_5 ": {: pnv 4000
1.02415e66

   pa 4000
1.03136e66

The memo adverb M. can be used to advantage here.

   pn =: -/@(+/)@:($:"0)@rec ` (x:@(0&=)) @. (0>:]) M.
   rec=: - (-: (*"1) _1 1 +/ 3 * ]) @ (>:@i.@>.@%:@((2%3)&*))

   pn 1000
24061467864032622473692149727991

Partitions with k Parts

An item of a partition is called a part. For example, the parts of the partition p=: 7 7 4 3 1 of 22 are 7, 7, 4, 3, and 1. p has 5 parts, and the largest part is 7.

   p=: 7 7 4 3 1

   #p
5
   >./p
7

   ] d=: p >/ i.7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 0 0 0
1 1 1 0 0 0 0
1 0 0 0 0 0 0
   +/"1 d
7 7 4 3 1
   +/d
5 4 4 3 2 2 2

The > function table formed by p and i.>./p is called a Ferrers diagram (say d). +/"1 d is the original partition, and +/d is also a partition of n .

If n pnk k is the number of partitions of n with largest part k , or equivalently, the number of partitions of n with k parts, then pnk satisfies the recurrence relation:

(n pnk k) = ((n-1) pnk k-1) + (n-k) pnk k

The recurrence relation is seen to be true by observing that the (n,k) partitions consist of those with exactly one k-part and those with two or more k-parts.

The recurrence relation can be implemented as a double recursion:

pnk=: 4 : 0 " 0
 n=. 0>.x [ k=. y
 if. 1>:n<.k do. x: (0<n)*1=k else. ((n-1) pnk k-1) + (n-k) pnk k end.
)

   pnk/~ i.11
0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0
0 1 2 1 1 0 0 0 0 0 0
0 1 2 2 1 1 0 0 0 0 0
0 1 3 3 2 1 1 0 0 0 0
0 1 3 4 3 2 1 1 0 0 0
0 1 4 5 5 3 2 1 1 0 0
0 1 4 7 6 5 3 2 1 1 0
0 1 5 8 9 7 5 3 2 1 1

   +/"1 pnk/~ i.11
0 1 2 3 5 7 11 15 22 30 42
   pnv 10
1 1 2 3 5 7 11 15 22 30 42

The double recursion in pnk makes it very slow even for small n . An iterative version is much more efficient.

pnkv=: 4 : 0 " 0
 n=. x [ k=. y
 j=. <"1 (1+i.k) */ _1 1
 t=. ((1+k)*(-*n),1) {. ,: 0 1x
 for. i.(1<k)*0>.n-1 do. t=. (}.t), (0,j{t) + |.!.''{:t end.
 {:t
)

   10 pnkv 5
0 1 5 8 9 7
   10 pnk i.6
0 1 5 8 9 7

   (pnkv~ i.11) -: pnk/~ i.11
1

   150 pnkv 5
0 1 75 1875 23906 187572
   150 pnk 5
187572

   ts=: 6!:2 , 7!:2@]  NB. time and space

   ts '150 pnkv 5'
0.00823792 8640
   ts '150 pnk 5'
21.9877 121280

pnkv returns the number of partitions for (n,0),...,(n,k). It is fast for small k but gets progressively slower (and consumes much space) with the growth of k.

The following function computes the number of partitions for (k,k),...,(n,k) and has a very different time-space model than pnkv. It is very fast as k approaching n but loses to pnkv in performance for small k.

pnkd=: 4 : 0
  m=. y <. s=. x-y
  t=. >:i.s
  p=. 1,s$0x
  for_i. >:i.m do.
    for_j. (<:i)}.t do. p=. (+/(j,j-i){p)j}p end. end.
)

   ts2=. 4 : '(ts ''x pnkv y'') ,: ts ''x pnkd y'''

   150 ts2 5
0.00300122  8576
 0.0267171 17920

   150 ts2 145
    1.52403 1.87238e6
0.000280762      5504

Essays/Partitions

Contents

All Partitions

The Number of Partitions

Partitions with k Parts

See also

Navigation menu

Search