There's more than one way to do things 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":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Please read these before you post! —
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?
• See Writeup Formatting Tips and other pages linked from there for more info.

Create A New User
Chatterbox?
 [marto]: tutorials-> Subroutines may be of interest [Corion]: A good morning to you too, marto! [marto]: hey Corion, good weekend? [prospect]: Thank you

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (8)
As of 2017-07-24 08:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (348 votes). Check out past polls.