Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

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!

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.


    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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://180309]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (10)
As of 2017-04-25 14:52 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (455 votes). Check out past polls.