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
