For example, let's say I have categories one through six with these respective heights (number of products):

  my @height = qw/ 10 15 25 30 10 13 /;
[download]

With that, I might have those categories distributed as follows (pretending that the index starts with 1 instead of zero):

The following code will accurately determine that, noting that I need to sort the actual values in each column. Further, it takes into account that the 1st and 6th category will always be in columns 1 and 4, respectively. Each for loop is iterating over a subsequent category with the indices being the only allowable values for a category (the second category is $a and cannot possibly be in column 3 because that would leave column 2 empty).

#!/usr/bin/perl -w
use strict;
use Data::Dumper;

my @height      = qw/ 10 15 25 30 10 13 /;
my @columns     = ($height[0],0,0,$height[-1]);
my $curr_height = 0;

# set this unreasonably high to ensure that subsequent
# heights will be lower
$curr_height    += $_ foreach @height;
my @distribution = ([1],[],[],[6]);

for my $a (0..1) {
    $columns[$a] += $height[1];
    for my $b (0..2) {
        $columns[$b] += $height[2];
        for my $c (1..3) {
            $columns[$c] += $height[3];
            for my $d (2..3) {
                $columns[$d] += $height[4];

                my $this_height = ( sort @columns )[-1];
                my $valid_dist;
                foreach ( @columns ) {
                    $valid_dist = $_;
                    last if ! $valid_dist;
                }
                if ( $valid_dist and $this_height < $curr_height ) {
                    $curr_height = $this_height;
                    push @{$distribution[$a]}, 2;
                    push @{$distribution[$b]}, 3;
                    push @{$distribution[$c]}, 4;
                    push @{$distribution[$d]}, 5;
                }
                $columns[$d] -= $height[4];
            }
            $columns[$c] -= $height[3];
        }
        $columns[$b] -= $height[2];
    }
    $columns[$a] -= $height[1];
}
print Dumper \@distribution;
[download]

That code results in 121 iterations. Some possibilities are skipped by last if ! $valid_dist because the for loops that I have written sometimes allow for invalid combinations (if the 5th category ($d) is in the fourth column, the 4th category cannot be in the second column because that would leave the third column empty).

My real problem: the client dictates changes to the Web site faster than a jackrabbit ... uh, never mind ... you get the idea.

Essentially, this used to be two columns. It's now four. It may turn into three columns. We may have another category added or removed. My code snippet works, but if the client changes his mind again, it would be nice to simply have the code work. Any suggestions?

Cheers,
Ovid

Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.