Kozz has asked for the wisdom of the Perl Monks concerning the following question:
Esteemed monks:
I've got data in an nbyn twodimensional array. Assuming that my n is divisible by two, I need to be able to iterate over the items in submatrices. 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 2dim 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 upperleft 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" (haha) 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 < ($size1) && (($row_num + 1) % $size > 0
+) ){
$row_num++;
$col_num=$max_part;
}
if($col_num < ($max_part1) && $row_num == ($size1)){
# $col_num++;
$row_num=$max_part;
$end_col+=$max_part;
}
if($col_num == ($size1) && $row_num < ($size1)){
$row_num++;
$col_num=$max_part;
}
if($col_num == ($max_part1) && $row_num == ($size1))
+{
$row_num++;
$col_num=0;
$end_col=$max_part;
}
$tiles_counted += $part_tiles_counted;
}
}
Re: Iterating over Blocks of 2Dim 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";
}
}
Update: added inverse operation.
 [reply] [d/l] [select] 

Thank you  brilliant! I'm also considering how to extend this concept in such a way that it subdivides beyond simple 4quadrants. Thanks for the inspiration.
 [reply] 
Re: Iterating over Blocks of 2Dim 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
 [reply] [d/l] 
Re: Iterating over Blocks of 2Dim 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 2D 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.
 [reply] 
Re: Iterating over Blocks of 2Dim 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_subs1) {
for $c (0 .. $num_col_subs1) {
for $sub_row (0 .. $rowstep1) {
for $sub_col (0 .. $colstep1) {
$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 forloops changes manner of walking through submatrices.  [reply] [d/l] 

