Looking at
ZZ 5 4
0 1 5 6
2 4 7 13
3 8 12 14
9 11 15 18
10 16 17 19
the coordinates of the subsequent layers are given by
(+/"1 <@|.`</. ]) (#: [EMAIL PROTECTED]/)5 4
+---+---+---+---+---+---+---+---+
|0 0|0 1|2 0|0 3|4 0|2 3|4 2|4 3|
| |1 0|1 1|1 2|3 1|3 2|3 3| |
| | |0 2|2 1|2 2|4 1| | |
| | | |3 0|1 3| | | |
+---+---+---+---+---+---+---+---+
If the coordinates of the zigzag order are observed carefully, one can
derive the specifications which are easily generalised to more than 2
dimensions.
a. zigzag numbers are ordered in diagonal layers (hyperplanes) of increasing
sum of cell indexes (coordinates), which sum is constant per hyperplane
b.a. subsequent zz-numbers in one hyperplane differ exactly +1 _1 in exactly
2 coordinates.
b.b. subsequent zz-numbers in two hyperplanes - the last one of the former
hp and the first one of the latter hp - differ exactly 1 in exactly 1
coordinate.
If these specs have to be applied to higher dimensions, than this can only
be successfully done with the help of generalised Gray codes.
Most of the code in 2 dimensions can be re-used in the new definition of ZZ:
ZZ=: $ ([: /:@;@(+/"1 <@|.`</. ]) (#: gGC7))
ZZ 2 3 4
0 1 8 9
2 7 10 19
6 11 18 20
3 4 14 15
5 13 16 22
12 17 21 23
Of course this works in 2 dimensions as well:
ZZ 5 4
0 1 5 6
2 4 7 13
3 8 12 14
9 11 15 18
10 16 17 19
The hyperplanes, layers with constant sum of coordinates, can be visualised
by
($[: (/:{+/"1)@;@(+/"1 <@|.`</. ]) (#: gGC7))5 4
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
and
($[: (/:{+/"1)@;@(+/"1 <@|.`</. ]) (#: gGC7))2 3 4
0 1 2 3
1 2 3 4
2 3 4 5
1 2 3 4
2 3 4 5
3 4 5 6
R.E. Boss
-----Oorspronkelijk bericht-----
Van: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Namens R.E. Boss
Verzonden: dinsdag 5 december 2006 17:09
Aan: 'Programming forum'
Onderwerp: RE: [Jprogramming] zig-zag order
AFAIK no solution followed your hint (constant sum layers),
so using /: and gerund argument of (dyadic!) /. of former solutions, I
constructed ZZ:
lr 'ZZ'
$ ([: /:@;@(+/"1 <@|.`</. ]) (#: [EMAIL PROTECTED]/))
ZZ 5 4
0 1 5 6
2 4 7 13
3 8 12 14
9 11 15 18
10 16 17 19
It appeared that Kobchenko's elegant solution
($ [: /:@; [: <@|.`</. i.)
was far less efficient:
5 ts'ZZ 500 400'
0.059869412 10989120
5 ts'($ [: /:@; [: <@|.`</. i.)500 400'
0.31710508 34260352
(ZZ -: ($ [: /:@; [: <@|.`</. i.))500 400
1
Probably monadic /. allows some improvement:
M=:500 400 [EMAIL PROTECTED] 10000
ts'(<@,{&.>~ <@$ #.&.> ([: (+/"1 </. ]) (#: [EMAIL PROTECTED]/)@$))M'
0.054501483 10992128
ts'</.M'
0.25997343 32161280
(</.-:(<@,{&.>~ <@$ #.&.> ([: (+/"1 </. ]) (#: [EMAIL PROTECTED]/)@$)))M
1
R.E. Boss
-----Oorspronkelijk bericht-----
Van: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Namens bill lam
Verzonden: zaterdag 25 november 2006 15:44
Aan: Programming forum
Onderwerp: [Jprogramming] zig-zag order
I found a problem that is said to an assignment for introductory C course
but it
turned to be not so trivial. It can be rephrased in J as: for a positive
integer
m find the array v or equivalently (m,m)$v so that result is a matrix with
atoms
of i.*:m filling in zig-zag order. (restricted to square matrix for time
being)
example
4 4$0 1 5 6 2 4 7 12 3 8 11 13 9 10 14 15
0 1 5 6
2 4 7 12
3 8 11 13
9 10 14 15
I tackled the problem by noticing the sum of cell index pair for each layer
is
constant but run into trouble when need to eliminate extra pairs after
passing
the middle layer.
All suggestions welcome.
PS. zig-zag order is used in jpeg encoding http://en.wikipedia.org/wiki/JPEG
--
regards,
bill
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
