 good chemistry is complicated,and a little bit messy -LW PerlMonks

Iterating over Blocks of 2-Dim Array

by Kozz (Friar)
 on Apr 01, 2004 at 02:49 UTC Need Help??

Kozz has asked for the wisdom of the Perl Monks concerning the following question:

Esteemed monks:

I've got data in an n-by-n two-dimensional array. Assuming that my n is divisible by two, I need to be able to iterate over the items in sub-matrices. Let me explain, and see if you can help me with this algorithm. I've tried, but can't quite wrap my head around it, and the code I DO make always tends to be far uglier than I'd expect it to be.

Disclosure: This is homework related. However, iterating over the data in this manner is not the main thrust of it. My "work" was done in the assignment of the 2-dim array elements' values. I just chose to break up the output into more manageable blocks (perhaps badly?).

Supposing n = 4, then I've got 4 "rows" of indices 0..3, each row having a "column" with indices 0..3, like this (vertical bars and dashed line to represent a line dividing matrix into quadrants):

[ 00 01 | 02 03 ] [ 10 11 | 12 13 ] ----------------- [ 20 21 | 22 23 ] [ 30 31 | 32 33 ]
I want to output the four elements in the upper-left quadrant of the matrix (00, 01, 10, 11, in that order), then upper right, lower left, lower right.

What trips me up is that I iterate over the first two cols of the first row, then increment row but reset cols. Then row gets reset and cols adjusted.... it's just a very awkward traversal of the matrix.

I know this is more of an algorithms question than a perl question, so smack me down with a -- if you must. But I know that there are monks that can likely whip up a very elegant solution for this.

Thanks for any insight you can provide.

Update: Code per request. This script was made just for a "simple" (ha-ha) base case to see if I could figure out how to iterate over pairs of indices in this manner. I know I've got an infinite loop, too, while I'm trying to figure out when to increment/decrement my rows & columns.

#!/usr/bin/perl my \$n = 2; my \$max_exp = 1; use strict; my \$max_part = 2**\$max_exp; my \$size = 2**\$n; print "Matrix is \$size by \$size.\n"; print "Max size I'm allowed to print is \$max_part at a time.\n"; my \$max_part_tiles = \$max_part**2; my \$total_tiles = (\$size)**2; my \$tiles_counted = 0; my \$part_tiles_counted = 0; my (\$row_num, \$col_num, \$end_col) = (0, 0); my (\$cols_displayed, \$rows_displayed) = (0, 0); while(\$tiles_counted < \$total_tiles){ \$col_num=0; \$end_col=\$max_part; while(\$row_num < \$size){ while(\$col_num < \$end_col){ print "\$row_num \$col_num\n"; \$col_num++; \$part_tiles_counted++; } if(\$col_num < (\$size-1) && ((\$row_num + 1) % \$size > 0 +) ){ \$row_num++; \$col_num-=\$max_part; } if(\$col_num < (\$max_part-1) && \$row_num == (\$size-1)){ # \$col_num++; \$row_num-=\$max_part; \$end_col+=\$max_part; } if(\$col_num == (\$size-1) && \$row_num < (\$size-1)){ \$row_num++; \$col_num-=\$max_part; } if(\$col_num == (\$max_part-1) && \$row_num == (\$size-1)) +{ \$row_num++; \$col_num=0; \$end_col=\$max_part; } \$tiles_counted += \$part_tiles_counted; } }

Replies are listed 'Best First'.
Re: Iterating over Blocks of 2-Dim Array
by kvale (Monsignor) on Apr 01, 2004 at 03:51 UTC
Algorithmically, you can think of this as a tensor product of 2 2x2 matrices. In code, you could represent this as
for my \$a (0,1) { for my \$b (0,1) { print "Quadrant \$a,\$b:\n"; for my \$i (0,1) { for my \$j (0,1) { my \$row = 2*\$a + \$i; my \$col = 2*\$b + \$j; print " element \$i,\$j => matrix coord \$row, \$col\n"; } } } }
If you wanted to convert in the opposite direction, just use the inverse equations:
for my \$row (0..3) { for my \$col (0..3) { print "Quadrant ", int(\$row/2),',',int(\$col/2); print " Element ", \$row % 2,',', \$col % 2,"\n"; } }

-Mark

Thank you -- brilliant! I'm also considering how to extend this concept in such a way that it subdivides beyond simple 4-quadrants. Thanks for the inspiration.
Re: Iterating over Blocks of 2-Dim Array
by BrowserUk (Patriarch) on Apr 01, 2004 at 03:58 UTC

#! perl -slw use strict; use Data::Dumper; # create matrix # # [ # [ a, b, c, d ], # [ e, f, g, h ], # [ i, j, k, l ], # [ m, n, o, p ], # ] my \$a = 'a'; my @a2d = map{ [ map{ \$a++ } 1..4 ] } 1..4; #print Dumper \@a2d; for my \$y ( 0, 2 ) { for my \$x ( 0, 2 ) { print @{ \$a2d[ \$y ] }[ \$x .. \$x+1 ]; print @{ \$a2d[ \$y+1 ] }[ \$x .. \$x+1 ], \$/; } } __END__ ab ef cd gh ij mn kl op

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Re: Iterating over Blocks of 2-Dim Array
by graff (Chancellor) on Apr 01, 2004 at 03:48 UTC
What trips me up is that I iterate over the first two cols of the first row, then increment row but reset cols. Then row gets reset and cols adjusted.... it's just a very awkward traversal of the matrix.
Well, maybe it seems awkward, but it sounds like basically the right approach. Perhaps if you showed us the relevant code snippet that walks through the array this way, we could comment on whether the code is awkward, given the intended method (which itself is not that bad).

I've used that sort of "hopping around" within a 2-D data space fairly often -- e.g. when laying out a grid of Tk widgets into related "quadrants"; doing modulo arithmetic and resetting indices from one quadrant to the next is an acceptable (and usually optimal) solution.

So if you think your code yucky, show it to us, so we can decide whether we agree with you.

Re: Iterating over Blocks of 2-Dim Array
by punchcard_don (Beadle) on Apr 01, 2004 at 13:20 UTC
For the general case of an n x m matrix:
(note n & m evenly divisible by i & j respectively)
\$rows = n; \$cols = m; \$rowstep = i; \$colstep = j; \$num_row_subs = \$rows/\$rowstep; \$num_col_subs = \$cols/\$colstep; for \$r (0 .. \$num_row_subs-1) { for \$c (0 .. \$num_col_subs-1) { for \$sub_row (0 .. \$rowstep-1) { for \$sub_col (0 .. \$colstep-1) { \$row = \$r*\$rowstep+\$sub_row; \$col = \$c*\$colstep+\$sub_col; print "[\$r*\$rowstep+\$sub_row = \$row][\$c*\$colstep+\$sub_ +col = \$col]<br>\n"; } } } }
Switching order of for-loops changes manner of walking through sub-matrices.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://341489]
Approved by davido
Front-paged by jweed
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2022-01-27 11:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2022, my preferred method to securely store passwords is:

Results (70 votes). Check out past polls.

Notices?