Probably why I continue having trouble solving those Project Euler problems involving partitions directly or indirectly... not to mention most other recent PE problems!
Cheers, Mike Please reply to mike_liz....@tiscali.co.uk. Sent from my iPad > On 17 Apr 2019, at 14:16, 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
