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
