Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Puzzle: need a more general algorithm

by fglock (Vicar)
on Jul 16, 2002 at 13:41 UTC ( #182075=note: print w/ replies, xml ) Need Help??


in reply to Puzzle: need a more general algorithm

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


    Comment on Re: Puzzle: need a more general algorithm
    Download Code
    Re: Re: Puzzle: need a more general algorithm
    by Anonymous Monk on Jul 17, 2002 at 00:38 UTC
      Did you miss Re: Balance columns?

      It gets correct answers, works fine with random numbers (as long as they are all non-negative), is linear in memory consumption and the running time is O(N*log(N)).

    Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Node Status?
    node history
    Node Type: note [id://182075]
    help
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others drinking their drinks and smoking their pipes about the Monastery: (7)
    As of 2014-07-12 11:49 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      When choosing user names for websites, I prefer to use:








      Results (239 votes), past polls