The late Howard Peelle covered this problem in depth: https://code.jsoftware.com/wiki/User:Devon_McCormick/HAP_AIP . There is also a general page on this problem: https://code.jsoftware.com/wiki/Essays/AllPartitions .
On Wed, Apr 17, 2019 at 9:17 AM Roger Hui <rogerhui.can...@gmail.com> wrote: > An amusing note about the memo operator and partition calculations. In *A > History of APL in 50 Functions <http://www.jsoftware.com/papers/50/>*, > chapter 16, it is estimated that computing pn 200 without memo, would > take 4.15407e34 years. > > On Wed, Apr 17, 2019 at 1:01 AM 'Mike Day' via Programming < > programm...@jsoftware.com> wrote: > > > Over breakfast just now, I've spotted two typos in my msg, below. It > > said "Sent from my iPad" which > > explains the two gratuitous capitalisations of " i. " below - they > > should have been " i.-3 " and " i.7 " > > While I have the opportunity, it's perhaps worth pointing out that the > > other J wiki recurrence relation verb, > > pnkv, also works here, so > > {:79 pnkv 7 > > 108869 > > {:79 pnkd 7 > > 108869 > > Roger's J-wiki essay may be found here: > > https://code.jsoftware.com/wiki/Essays/Partitions > > "Nimp O's" contribution uses this recurrence relation too, as noted in > > that later message. > > Cheers, > > Mike > > > > PS - while we're about it, some time and space consumption: > > > > ts'{:79 pnkv 7' NB. good for relatively low y vs x > > 0.0002257 15808 > > ts'{:79 pnkd 7' NB. good for y approaching x > > 0.000465978 7488 > > ts'#7 mpart 79' NB. not too bad for creating lists of m-partitions ! > > 0.0889004 2.83149e7 > > > > On 17/04/2019 00:21, 'Mike Day' via Programming wrote: > > > I’ve worked up a number of variant explicit partition functions. One of > > these is mpart; > > > m mpart n yields all m-partitions of n, with no zeros, but allowing > > repeats. > > > > > > So, for example, using a smallish example: > > > 3 mpart 7. NB. there are four 3-partitions of 7 > > > 3 2 2 > > > 3 3 1 > > > 4 2 1 > > > 5 1 1 > > > > > > This can lead to all 3-partitions of 10 excluding repeats as follows: > > > 2 1 0 + "1] 3 mpart 7. NB. add I.-3 to 3-partitions of 7=10-3 > > > 5 3 2 > > > 5 4 1 > > > 6 3 1 > > > 7 2 1 > > > (#~ 3=#@~."1) 3 mpart 10 NB. naive way, filter 3-partitions of 10 > > for non-repeats > > > 5 3 2 > > > 5 4 1 > > > 6 3 1 > > > 7 2 1 > > > > > > Count numbers of m-partitions of 7 for m = 1,7: > > > (>:i. 7)#@ mpart"0]7 > > > 1 3 4 3 2 1 1 > > > > > > Here, however, you want 7-partitions of 100 without repeats, which can > > be derived from > > > 7-partitions of 79 = 100- +/ I.7 > > > > > > Perhaps surprisingly, mpart does manage to cope with this size of > > problem: > > > #7 mpart 79 > > > 108869 > > > > > > You’ll find essays on partitions at J Wiki, including partition > counting > > functions, pnkv and pnkd. > > > This is somewhat quicker than my constructive verb: > > > {:7 pnkd~ 79 > > > 108869 > > > > > > Note that these both count partitions excluding zero elements, whereas > > your odo appears to include zeros. Since you require all elements > > different, I suppose you might wish to include 6-partitions as well. I > > won’t attempt that here. > > > > > > I’ll list my mpart and pnkd, which I think was one of Roger’s > offerings: > > > > > > NB. my function for m-partitions of n where x = m & n = y > > > mpart =: 3 : 0 > > > : > > > m =. x [ n =. y > > > NB. smoutput m;n > > > if. m = 1 do. ,: n return. end. > > > max =. n + 1 - m > > > min =. >.n%m > > > l =. ,.min ([+i.@>:@-~ ) max > > > for_j. >:}:}. i.m do. > > > rem =. n - +/"1 l > > > min =. >. rem%(m + 1 - j) > > > max =. min >. ({:"1 l) <. rem - m - j > > > nl =. 0-.~, min ([+i.@>:@-~ )"0 max > > > l =. nl,.~ l#~1 + max - min > > > end. > > > l,. n - +/"1 l > > > ) > > > > > > NB. If n pnk k is the number of partitions of n with largest part k , > > > NB. or equivalently, the number of partitions of n with k parts, then > > > NB. pnk satisfies the recurrence relation: > > > NB. (n pnk k) = ((n-1) pnk k-1) + (n-k) pnk k > > > NB. > > > NB. partition number functions > > > NB. The following function computes the number of partitions for > > (k,k),...,(n,k) > > > NB. and has a very different time-space model than pnkv. > > > NB. It is very fast at k approaching n but loses to pnkv in performance > > for small k. > > > NB. n pnkd k : for [k,n] efficient for large 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. > > > ) > > > > > > Hope that’s what you wanted, > > > > > > Mike > > > > > > > > > Sent from my iPad > > > > > >> On 16 Apr 2019, at 22:13, 'Skip Cave' via Programming < > > programm...@jsoftware.com> wrote: > > >> > > >> I ran across this problem on Quora... How many ways can 100 be written > > as a > > >> sum of 7 ordered positive integers? (no repeats) > > >> The obvious brute force approach in J would be: > > >> > > >> > > >> odo=: #: i.@(*/) NB. Odometer verb > > >> > > >> #b=.~./:~"1 a#~100=+/"1 a=.odo 7#100 > > >> > > >> |limit error: odo > > >> > > >> | #b=:~./:~"1 a#~100=+/"1 a=: odo 7#100 > > >> > > >> Of course, odo 7#100 generates 1e14 integers (100^7) which exceeds > > memory. > > >> > > >> So what would the most efficient way to solve this question in J? The > > most > > >> concise? > > >> > > >> > > >> Skip > > >> > > >> Skip Cave > > >> Cave Consulting LLC > > >> ---------------------------------------------------------------------- > > >> For information about J forums see > http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > --- > > This email has been checked for viruses by Avast antivirus software. > > https://www.avast.com/antivirus > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm -- Devon McCormick, CFA Quantitative Consultant ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
