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
> <[email protected]> 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
