Here's a partition function in the sense of counting
of sums by coin size. It uses the Memo class that
Oleg did most of the work on.
Partition =: 4 : 0
NB. x is sum, y list of coins to make sum.
NB. presume y is sorted up. (replace r with appends to
list instead of count)
r=.0
for_i. i.#y do.
y0=.i_index{ y
a=.x - y0
newy=.((y0&>:)# ])y
r=. r + (a e. newy)
if. a<2*{.y do. continue. end.
r=. r+ ( a Partition newy)
end.
r
)
Partition =: Partition f. Memo
ways to get canadian change for a toonie
200 Partition 1 5 10 25 100
1706
ways to make the sum of 50 with digits 1to49
50 Partition (1+i.49)
204225
Memo class
---------------
coclass'Memo'
lastobj=: ''
create=: 3 : 0
KEY=: ''
VAL=: ''
)
destroy=: codestroy
find=: 3 : 0
if. (#KEY)>i=.KEY i. y do.i{::VAL else. '' end.
)
set=: 4 : 0
KEY=: KEY,< x
VAL=: VAL,< y
)
mv=: 2 : 0
if.0=#r=.find__n<y do.y set__n r=.u y end.r
:
key=. (x;y)
if.0=#r=.find__n <key do.key set__n r=.x u y end.r
)
cocurrent 'base'
Memo=: 1 : 0
lastobj =: (''conew'Memo')
u mv_Memo_ lastobj
)
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
