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 at
http://www.jsoftware.com/help/dictionary/vocabul.htm
|
