in reply to Puzzle: need a more general algorithm
Thinking vaguely...
Notation:
 Columns: N
 Category count: Q
Assuming the problem makes sense (Q>N), yet another way to think about the problem space is to enumerate the cells like this:
1 3 5 7 2 4 6 8
Then, if we index the categories by 0...Q1 (fine because the category order must be preserved), we can consider the location of a category to be L(category index).
The nature of this location is yet to be determined.
I see that the categories always fill up from the top down.
Now, implementation details are critical...so I may be off on a wild goose chase. I'm envisioning this target (X)HTML table as a single row with a single cell for each column. Then the topdown ordering is automatic, and we're just calculating where to put the table cell delimiters. In this case, the location L corresponds simply to the column, and I can forget about rows entirely for the analysis. Then
L(0)<=L(1)<=...<=L(Q2)<=L(Q1)
In particular, L(0)=1 and L(Q1)=N. In some way, we need to track the mininum category index for each column 2...N.
Merlyn pointed out the above, in his comment about binary representation.
Untested pseudocode follows:
my $ColumnCount = 4; # or whatever we need it to be
my $CategoryCount = 6; # or whatever we need it to be
my %Weight = ();
# TODO: initialize %Weight hash with values from 0 to Q1
my %WeightCache = (); # to be filled with weights
# TODO: initialize weight cache to handle references to
# hashes with indexes 1..Q1
# bruteforce would iterate across combinations of 1...Q1;
# for 6 categories and 4 columns, this is 5 choose 3 i.e. 10
sub WeightSpan
{
my ($LowBound,$HighBound) = @_;
my $WeightSum = 0;
$WeightSum += $Weight{$LowBound++}
while $LowBound<$HighBound;
return $WeightSum;
}
sub IncrementCombination
{
my ($LowBound,$HighBound,@Combination) = @_;
my $Idx = 0;
while($Combination[$Idx1]=$HighBound$Idx)
{
return () if 1==$Idx+scalar @Combination;
$Idx;
};
$Combination[$Idx1]++;
$Combination[++$Idx 1]++ while $Idx;
return @Combination;
}
sub MaximumHeight
{
my ($LowBound,$HighBound,@Combination) = @_;
my @IndexSpan = ();
# TODO: autoinit @IndexSpan: 0...scalar @Combination1
return max(map
{$WeightCache{$Combination[$_]}{$Combination[$_+1]}
= &WeightSpan($Combination[$_],$Combination[$_+1])}
@IndexSpan);
}
sub CrunchBestCombination
{
my ($LowBound,$HighBound,$N) = @_;
my @Combination = ();
# TODO: autoinit: fill @Combination with 1...$N1
my @BestCombination = @LowestBounds;
my $BestHeight = &MaximumHeight($LowBound, $HighBound,
@Combination);
&IncrementCombination($LowBound, $HighBound,
@Combination);
while(@Combination)
{
my $CurrentMaxHeight =
&MaximumHeight($LowBound,$HighBound,@Combination);
if ($CurrentMaxHeight<$BestHeight)
{
$BestHeight = $CurrentMaxHeight;
@BestCombination = @Combination;
}
@Combination = &IncrementCombination($LowBound,
$HighBound, @Combination);
}
return ($BestHeight,@BestCombination);
}
my @TargetCombination = &CrunchBestCombination(1,
$ColumnCount1, $CategoryCount);
my $BestHeight = shift(@TargetCombination);
# TODO: translate @TargetCombination into </td><td>
# cell breaks
Obviously, all TODO comments should be implemented before the code has any chance of working. Also, a number of the example functions can be made more succinct.
