There is a very fast method based on the doubly recursive
definition of comb. From the M. page of the dictionary
http://www.jsoftware.com/help/dictionary/dmcapdot.htm :
comb=: 4 : 0 M. NB. All size x combinations of i.y
if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x comb&.<: y),1+x comb y-1 end.
)
The direct method:
cs=: 4 : 0
({.,#)/.~ +/"1 x comb y
)
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
3 cs 5
3 1
4 1
5 2
6 2
7 2
8 1
9 1
The fast method derives from the doubly-recursive
defn of comb: combination sums are computed for
(x-1) combsum y-1 and x combsum y-1 ; combine
these appropriately to produce x combsum y . Thus:
combsum=: 4 : 0 M.
if. (x>:y)+.0=x do. ,: 1 ,~ +/"1 i.(x<:y),x
else. ([EMAIL PROTECTED] ,. +//.)/ |: (((x-1),0)+"1 x combsum&<: y),(x,0)+"1 x
combsum y-1 end.
)
3 (cs -: combsum) 5
1
6 (cs -: combsum) 10
1
6 (cs -: combsum) 11
1
To correct for the 1-origin indexing in the original
problem, just add x to column 0 of the result.
(Due to the use of M., reload the script or otherwise
redefine comsum to get true timing.)
6!:2 't=. 6 0 (+"1) 6 combsum 49'
0.0252536
$t
259 2
3{.t
21 1
22 1
23 2
_3{.t
277 2
278 1
279 1
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Tuesday, April 29, 2008 8:44
Subject: [Jprogramming] sums of combinations
To: Programming forum <[email protected]>
> An amusing puzzle from comp.lang.apl posted on 2008-04-23
> http://groups.google.com/group/comp.lang.apl/browse_thread/thread/1836e834b63cfb29/f2a9ba479d6419b0?lnk=gst&q=%2244%2C45%2C46%22#f2a9ba479d6419b0
>
> Take the UK national lottery - it has 6!49 combinations where
> the
> first (1,2,3,4,5,6) and the last (44,45,46,47,48,49) have each
> got a
> sum and the number of combinations that have the same respective
> sum is exactly 1. The objective was to list each sum between the
> 2 with the number of combinations ... quickly. After a lot of
> experimentation,
> the solution ran in less than 2 minutes on a 1.6 GHz Pentium
> processor.
>
> ({.,#)/.~ +/"1 ] 6 comb 49
>
> The array 6 comb 49 would require at least */4 6,6!49 or
> 335611584 bytes.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
