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:
and checked using an asymptotic formula by Hardy and Ramanujan:
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
See also
Contributed by Roger Hui. Additions by Boyko Bantchev