[Jprogramming] Quora problem

[Nimp O]

My solution is based on the following recurrence formula of the generating function:  h(m,n) = h(m,n-m) + h(m-1, n-m).
Memoizing, as Roger pointed, helps a lot. The agenda is used to handle the edge cases such as negative n or h(0,0) = 1.

h=:1:`0:`0:`(([h-~)+(<:@[h-~))`0: @.(#.@(,&*)) M.

   7 h 100
108869
________________________________
From: Programming <programming-bounces at forums.jsoftware.com> on behalf of 'Skip Cave' via Programming <programming at jsoftware.com>
Sent: Tuesday, April 16, 2019 5:13 PM
To: Programming at jsoftware.com
Subject: [Jprogramming] Quora problem

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