On Apr 30, 10:09 am, RHui...@[EMAIL PROTECTED]
wrote:
> On Apr 29, 10:34 pm, AAsk <AA2e...@[EMAIL PROTECTED]
> wrote:
>
> >http://www.jsoftware.com/jwiki/Essays/Combination_Sums
>
> > I like the template/style used to present the solution very much.
>
> > I am somewhat ashamed by my own illiteracy in J; this is so severe
> > that I cannot even begin to make sense of the code. I know that J has
> > (some) language structures/enhancements that simply do no exist in
> > APL; nonetheless, can someone translate this into APL?
>
> > [There is only so much time to learn new things.]
>
> The problem is to find the distinct sums of
> all combinations and their counts. For example:
>
> NB. all size 3 combinations of i.5
> 3 comb 5
> 0 1 2
> 0 1 3
> 0 1 4
> 0 2 3
> 0 2 4
> 0 3 4
> 1 2 3
> 1 2 4
> 1 3 4
> 2 3 4
> NB. sum of each combination
> +/"1 ] 3 comb 5
> 3 4 5 5 6 7 6 7 8 9
>
> NB. distinct sums and counts
> 3 cs 5
> 3 1
> 4 1
> 5 2
> 6 2
> 7 2
> 8 1
> 9 1
>
> cs can be defined succinctly:
>
> cs=: 4 : '({.,#)/.~ +/"1 x comb y'
>
> The key is the use of /. , the "key" adverb.
> In x u/. y, items of x specify keys for
> corresponding items of y and u is applied to
> each collection of y having identical keys.
> Here, x and y are both the combination sums,
> and u is the verb ({.,#), "first" catenated
> with "count". Thus:
>
> s=: +/"1 ] 3 comb 5
> s
> 3 4 5 5 6 7 6 7 8 9
> s ({.,#)/. s
> 3 1
> 4 1
> 5 2
> 6 2
> 7 2
> 8 1
> 9 1
>
> Use of < (box) elucidates the action of the
> adverb:
>
> s </. s
> +-+-+---+---+---+-+-+
> |3|4|5 5|6 6|7 7|8|9|
> +-+-+---+---+---+-+-+
> </.~ s
> +-+-+---+---+---+-+-+
> |3|4|5 5|6 6|7 7|8|9|
> +-+-+---+---+---+-+-+
>
> cs, while direct, is not very efficient.
> The intermediate array x comb y has shape
> (x!y),x , requiring */4,x,x!y bytes. In the
> original "national lottery" problem, x=:6 and
> y=:49, requiring */4,6,6!49 or 335611584 bytes.
> We derive an alternative computation combsum
> which is sufficiently efficient to calculate
> 50 combsum 100 in a couple of seconds.
>
> The method derives from the classic
> doubly-recursive definition of comb ,
> "classic" because the same algorithm can be
> found in Gilman & Rose, "APL\360 An
> Interactive Approach".
>
> comb=: 4 : 0 M.
> if. (x>:y)+.0=x do.
> i.(x<:y),x
> else.
> (0,.x comb&.<: y),1+x comb y-1
> end.
> )
>
> x comb y is 1+(x-1) comb y-1 prefaced with an
> initial column of 0, catenated to 1+x comb y-1 .
> M. is the "memo" adverb; u M. is the same as
> u but but may keep a record of the arguments
> and results for reuse. The use of M. makes
> this double-recursive definition competitive
> with more complicated statements of comb .
>
> The result of combsum is a 2-column matrix
> of the sums and counts. Analogs are needed
> to the recursive steps 0,.1+(x-1) comb y-1
> and 1+x comb y-1 . For the first, prefacing
> with a column of 0 changes neither the sums
> nor the counts, and adding by 1 increases each
> sum by x-1 (because there are x-1 entries in
> each combination) and changes the counts not
> at all. Thus: ((x-1),0)+"1 (x-1) combsum y-1 .
> For the second, adding by 1 increases each
> sum by x (and does not change the counts).
> Thus: (x,0)+"1 x combsum y-1 . It remains
> to merge these parts together to form a
> single (sums,counts) result.
>
> If p=.p0,p1 is the catenation of the two parts,
> whose column 0 s is the catenated sums and
> whose column 1 c is the catenated counts,
> then the overall list of sums is just the nub
> of the sums, i.e. ~.s , and the overall list of
> counts is s+//.c , the counts accumulated
> according to the sums. This is accomplished
> by (~.@[EMAIL PROTECTED]
,. +//.)/ |:p , inserting the verb
> (~.@[EMAIL PROTECTED]
,. +//.) between the rows of the
> transpose of p . Putting it all together:
>
> combsum=: 4 : 0 M.
> if. (x>:y)+.0=x do.
> (x<:y)#,:2!x,2
> else.
> (~.@[EMAIL PROTECTED]
,. +//.)/ |: (((x-1),0)+"1 x combsum&<: y),(x,0)+"1 x combsum
> y-1
> end.
> )
>
> (Some lines above may be wrapped by the msg
> transmission software.)
>
> The original "national lottery" problem uses
> 1-origin (the first combination is 1 2 3 4 5 6
> instead of 0 1 2 3 4 5); just add 6 to each
> sum to account for that. Thus:
>
> 6!:2 't=: 6 0 (+"1) 6 combsum 49'
> 0.0250315
>
> That is, the result is computed in 0.025 seconds
> (2.2 GHz Athlon 3200+). The shape of t and its
> first and last 4 rows:
>
> $t
> 259 2
> 4{.t
> 21 1
> 22 1
> 23 2
> 24 3
> _4{.t
> 276 3
> 277 2
> 278 1
> 279 1
>
> The sum of the counts should be 6!49 :
>
> +/ t
> 38850 13983816
> 6!49
> 13983816
>
> As promised:
>
> 6!:2 't=: 50 combsum 100'
> 2.05181
> $t
> 2501 2
> +/ t
> 6.18998e6 1.00891e29
> 50!100
> 1.00891e29
>
> I am curious how Dynamic Functionistas would
> solve this problem.
>
> I did not explain combsum and its derivation
> down to the details of every J primitive.
> If you wish to pursue that you can find the
> reference manual athttp://www.jsoftware.com/help/dictionary/vocabul.htm
The computation can be simplified and made
more efficient by observing that column 0 of
x combsum y is always (2!x)+i.1+x*y-x .
Thus:
cs2=: 4 : '((2!x)+i.1+x*y-x) ,. x cs2a y'
cs2a=: 4 : 0 M.
if. (x>:y)+.0=x do. (x<:y)$1
else. (m{.x cs2a&<:y) + (-m){.x cs2a y-1 [ m=. 1+x*y-x end.
)
(6 combsum 49) -: 6 cs2 49
1
|
