Beefy Boxes and Bandwidth Generously Provided by pair Networks httptech
Don't ask to ask, just ask
 
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
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
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.

Log In?
Username:
Password:

What's my password?
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 having an uproarious good time at the Monastery: (4)
As of 2014-04-21 08:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (492 votes), past polls