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...Q-1 (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 top-down 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(Q-2)<=L(Q-1)
In particular, L(0)=1 and L(Q-1)=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 pseudo-code 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 Q-1
my %WeightCache = (); # to be filled with weights
# TODO: initialize weight cache to handle references to
# hashes with indexes 1..Q-1
# brute-force would iterate across combinations of 1...Q-1;
# 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[$Idx-1]=$HighBound-$Idx)
{
return () if 1==$Idx+scalar @Combination;
$Idx--;
};
$Combination[$Idx-1]++;
$Combination[++$Idx -1]++ while $Idx;
return @Combination;
}
sub MaximumHeight
{
my ($LowBound,$HighBound,@Combination) = @_;
my @IndexSpan = ();
# TODO: auto-init @IndexSpan: 0...scalar @Combination-1
return max(map
{$WeightCache{$Combination[$_]}{$Combination[$_+1]}
||= &WeightSpan($Combination[$_],$Combination[$_+1])}
@IndexSpan);
}
sub CrunchBestCombination
{
my ($LowBound,$HighBound,$N) = @_;
my @Combination = ();
# TODO: auto-init: fill @Combination with 1...$N-1
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,
$ColumnCount-1, $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.
-
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.