Perl Monk, Perl Meditation PerlMonks

### Re: Puzzle: need a more general algorithm

by dws (Chancellor)
 on Jul 08, 2002 at 20:25 UTC ( #180309=note: print w/replies, xml ) Need Help??

in reply to Puzzle: need a more general algorithm

To distribute N categories across M columns as evenly as possible, assuming N >= M, observe that

1. (N mod M) columns will contain ((N div M) + 1) categories
2. the remaining (M - (N mod M)) columns, if any, will contain (N div M) categories.

Given this, categories can be distributed in one pass.

Update: Oh blast. I may have misread the problem, and confused the "height of the table in rows" with "the aggregate height summed from the @height data".

• Comment on Re: Puzzle: need a more general algorithm

Replies are listed 'Best First'.
Re(2): Puzzle: need a more general algorithm
by FoxtrotUniform (Prior) on Jul 08, 2002 at 20:37 UTC

Keep in mind that this is a weighted distribution: three categories with weight 10 are worth one category with weight 30 (so if N=2, you'd want 3/1 rather than 2/2).

This looks to me like a constrained (order must not change) variant on the bin packing problem. Bin packing is NP-complete in the general case (IIRC), but the order constraint makes this quite tractable (see merlyn's typesetting comment). This problem has a rather good (n lg n or n^2) solution via dynamic programming: the typesetting problem was on one of my assignments in an advanced algorithms class. (Hey, did Ovid just post a homework problem? ;-b) I'll dig through my old notes when I get home from work and see if I can find it. In the mean time, you (Ovid) might look at Text::Format for ideas.

Update: D'oh! Another constraint on the text formatting problem that isn't present here is a maximum on line length (bin size), which makes it hard to reject a bogus solution (too much in one bin) quickly. On the other hand, this solution is constrained by number of bins, which the text formatting solution isn't. Hmm.... (Great problem, Ovid!)

--
The hell with paco, vote for Erudil!
:wq

Re: Re: Puzzle: need a more general algorithm
by Ovid (Cardinal) on Jul 09, 2002 at 02:56 UTC

It appears that I have confused a few people here. What I need "minimized" is the aggregate height per column as summed from @height data.

Given the heights of qw/ 10 10 15 20 10 10 /, I could conceivably construct a table with no column having greater than 20 items in it:

```  10  15  20  10
10          10

The following solution, would fail because one of the columns has 25 items:

```  10  10  20  10
15      10

Part of the problem, I suspect, is that I had a bug in my original code because I accidentally posted the wrong version. The @distribution array needs to be reset every iteration. The following is correct:

```#!/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;

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;
@distribution = ([1],[],[],[6]);
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;

I hope that's clear, now :)

I also have to add that there's a heck of a lot more discussion on this than I thought there would be.

Cheers,
Ovid

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

Re: Re: Puzzle: need a more general algorithm
by japhy (Canon) on Jul 08, 2002 at 20:30 UTC
This seems to blur the lines of the original problem. There might be 103 categories to distribute, but they have to appear in chunks of 10, 15, 25, 30, 10, and 13.

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

Re: Puzzle: need a more general algorithm
by ferrency (Deacon) on Jul 08, 2002 at 20:33 UTC
This is true if your categories all have equal heights. But an optimal solution for a wide height distribution might place, for example, three categories in one column, and one category in each of the other three columns. A sample dataset for which that would be the optimal solution:

```my @heights = (4, 4, 4, 1, 1, 1); # in 4 columns
Alan

Create A New User
Node Status?
node history
Node Type: note [id://180309]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (4)
As of 2019-12-09 01:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?