Iterating over Blocks of 2-Dim Array

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 ]
[download]

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;
        }

}
[download]

Comment on Iterating over Blocks of 2-Dim Array Select or Download Code

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"; } } } }` [download] 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"; } }` [download] Update: added inverse operation. -Mark	[reply] [d/l] [select]
Re: Re: Iterating over Blocks of 2-Dim Array by Kozz (Friar) on Apr 01, 2004 at 04:11 UTC
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.	[reply]
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` [download] 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 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.	[reply]
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"; } } } }` [download] Switching order of for-loops changes manner of walking through sub-matrices.	[reply] [d/l]

Back to Seekers of Perl Wisdom