Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

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

    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!
  • 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
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others about the Monastery: (14)
    As of 2014-09-18 12:51 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (114 votes), past polls