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-boun...@forums.jsoftware.com> on behalf of 'Skip Cave' via Programming <programm...@jsoftware.com> Sent: Tuesday, April 16, 2019 5:13 PM To: programm...@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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
