Tried
kCnM=: 4 : 0 M.
if. x>:#y do. y
else. if. x>1 do. (({.y),.(x-1)kCnM}.y),x kCnM}.y
else. ,.y end.
end.
)
but even then
et '6 kCnM r' NB. first call; et=:6!:2
0.078162731
et '6 combM 16' NB. first call; et=:6!:2
0.0031360018
ts '6 comb2 r'
0.0011766047 603712
where
combM=: 4 : 0 M. NB. All size x combinations of i.y
if. (x>:y)+.0=x do. i.(x<:y),x else. (0,.x combM&.<: y),1+x combM y-1 end.
)
and
comb2=: 4 : 0 NB. All size x combinations of y
d=. x-~#y
k=. |.(>:d),\y
z=. (d$<i.0 0),<i.1 0
for_j. k do. z=. j ,.&.> ,&.>/\. z end.
; z
)
Check:
6 (((kCnM i.),:combM)-:"_1 _ (comb2 i.)) 16
1 1
Remarkable is that
5 et '6 combM 16' NB. from 2nd call on
1.5653098e_5
was a lot better compared to timing of first call, but
5 et '6 kCnM r' NB. from 2nd call on
0.078623575
showed no improvement.
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: [EMAIL PROTECTED] [mailto:programming-
> [EMAIL PROTECTED] Namens Arie Groeneveld
> Verzonden: donderdag 15 november 2007 18:45
> Aan: Programming forum
> Onderwerp: [Jprogramming] Combinations (again)
>
> I know there are already some very smart solutions
> for 'all combinations of length k taken from a set
> of length n' f.e. comb1 and combM cooked by R.E. Boss.
>
> I'm just curious. Is the double recursive method
> being considered to be a dead end for J or was it just
> a starting point to attack the problem with all the
> powerful possibilities of J?
>
> Anyway, here's my formulation of combinations, considering
> values of x outside the range of (x>0)*.x<:#y as nonsense:
>
> kCn=: 4 : 0
> if. x>:#y do. y
> else. if. x>1 do. (({.y),.(x-1)kCn}.y),x kCn}.y
> else. ,.y end.
> end.
> )
>
> I avoided the use of elseif. (ending in a useless test)
> and a temp var. for }.y
> By limiting x on the low side to a minimum of 1
> gives me also a considerable speed advantage:
> I mean instead of doing:
>
> else. if. x>0 do. (({.y),.(x-1)kCn}.y),x kCn}.y
> else. 1 0$0 end.
> )
>
>
> 2 kCn 'abcd'
> ab
> ac
> ad
> bc
> bd
> cd
>
> But
> r=: i.16
>
> ts '6 comb1 r'
> 0.00161 604224
>
> compared to
>
> ts '6 kCn r'
> 0.105149 593152
>
> Is there further improvement possible?
> without the use of helper functions :-)
>
>
>
> =@@i
>
>
> +/3&u: 'J.SOFT 6.02'
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
