# Essays/Partitions

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: ${\displaystyle 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: ${\displaystyle 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
`