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
