Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

comment on

( #3333=superdoc: print w/replies, xml ) 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

    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.
    Log In?

    What's my password?
    Create A New User
    Domain Nodelet?
    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
    Find Nodes?
      Voting Booth?
      Which type of climate do you prefer to live in?

      Results (61 votes). Check out past polls.