I would not use A. when building sets.
Instead:
sets=: (*"1 [: #:@i. 2^#)1+i.9
sums=: +/"1 sets
Ns=: +/"1 *sets
sol=:4 :0
0 -."1~ sets #~ (x=Ns)*y=sums
)
4 sol 12
1 2 4 5
1 2 3 6
timespacex '4 sol 12'
2.8e_5 9472
timespacex '9 sol 45'
1.6e_5 8960
Seems efficient enough to me?
Thanks,
--
Raul
On Sat, Aug 8, 2015 at 4:12 PM, Yoel Jacobsen <yoel.jacob...@gmail.com> wrote:
> I tried to follow Dan Baronet's "A tool of thought" in the latest Vector
> (26, 2&3). It's about solving Kankuro puzzles:
>
> Find all sets of N unique positive single digit numbers (1..9) making the
> sum S.
>
> I tried from scratch with J:
>
> sol =: dyad define
>
> p =. (i.!9) A. >: i. 9
>
> c =. ~. /:~"1 (x {."1 p)
>
> k =. (+/"1 c) = y
>
> k # c
>
> )
>
>
> so:
>
> 4 sol 12
>
> 1 2 3 6
>
> 1 2 4 5
>
>
> Clearly it's an efficient brute force algorithm. I wonder what would be the
> next optimization direction?
>
>
> A simple one would be using the first !8 x (10 - x) permutations, but for
> smaller values of x (such as 4 in the example above), the saving isn't big
> enough.
>
>
> Currently I explore calculating which permutations I actually need. I
> figured its related to !(9-x). For instance, the first (of 126) indexes for
> x = 4 are:
>
>
> 0 120 240 360 480 600 840 960 1080 1200 1320 1680 1800 1920 2040 2520 2640
> 2760 3360 3480 4200 5880 6000 6120 6240 6360 6720 ...
>
>
> The distances are:
>
> 0 120 120 120 120 120 240 120 120 120 120 360 120 120 120 480 120 120 600
> 120 720 1680 120 120 120 120 360 120 120 120 480 120 120 600 120 720 2520
> 120 120 120 480 120 120 600 120 720 3360 120 120 600 120 720 4200 120 720
> 5040 16800 ...
>
>
> I couldn't get the pattern yet, or the reason.
>
> .
>
> Ideas?
>
>
> Yoel
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
