No such thing as a small change PerlMonks

comment on

 Need Help??

This is the implementation I liked best (so far):

```# find subgroups with *almost* optimal sum distribution.
# performance is roughly linear on N and Columns.

use strict;
my \$benchmark;

sub splitter {
my (\$columns, \$plist) = @_;
return \$plist unless --\$columns;
my \$sum1 = 0;    my \$sum2 = eval join "+" => @\$plist;
my @tmp1 = ();   my @tmp2 = @\$plist;
my @best = (1e9, undef, undef);
while (\$#tmp2 > 0) {
\$benchmark++;
push @tmp1, shift @tmp2;
\$sum1 += \$tmp1[-1];
my \$mean_ratio = \$sum1 * \$columns / (\$sum2 - \$sum1);
\$mean_ratio = 1 / \$mean_ratio if \$mean_ratio < 1;
last unless \$best[0] > \$mean_ratio;
@best = (\$mean_ratio, [@tmp1], [@tmp2]);
}
return \$plist if \$best[0] == 1e9;   # underflow
return \$best[1],
\$columns > 0 ? splitter(\$columns, \$best[2]) : \$best[2];
}

my @list = (10, 15, 25, 30, 10, 13);
for my \$columns (3, 4, 5) {
\$benchmark = 0;
print "[", map(" [@\$_]", splitter(\$columns, \@list ) ), " ]\n\n";
print "Inner loop = \$benchmark\n\n";
}

my @list = (1..150);
for my \$columns (10, 50, 80, 100) {
\$benchmark = 0;
print "[", map(" [@\$_]", splitter(\$columns, \@list ) ), " ]\n\n";
print "Inner loop = \$benchmark\n\n";
}

Although this does not always give an exact solution, it has some advantages:

• it is pretty fast
• it is not memory-hungry
• it works fine with random numbers
• time is linearly proportional to number of columns and to list size
• I think it might be possible to find a better solution in time O(N * columns * log(N * columns)), by making the inner loop recursive.

update: it might be easy to rewrite "splitter" to don't use recursion, since it calls itself from outside the while loop

In reply to Re: Puzzle: need a more general algorithm by fglock
in thread Puzzle: need a more general algorithm by Ovid

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• 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.

Create A New User
Domain Nodelet?
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: (5)
As of 2023-03-24 17:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Which type of climate do you prefer to live in?

Results (61 votes). Check out past polls.

Notices?