comment on

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]

In reply to Iterating over Blocks of 2-Dim Array by Kozz

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Come for the quick hacks, stay for the epiphanies.
	PerlMonks