# 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";
}