S'funny? It doesn't do that for me:

c:\test>708290 -V -S=0 11 39 62

[11 62] := 73
[39] := 39
        [S:0]   [iters] Diff: 34
[download]

Non-optimum, but...

The only way I can reproduce that problem is if I supply 0 (zero) for the number of iterations (The first parameter). Is that what you have done? Because 0 iterations means "Do nothing".

I have no idea this is what I run:


#! perl -slw
use strict;
use List::Util qw[ sum shuffle ];

for (
    [ 22, 27, 57],
    [ 11, 62, 39],
) {
    my( $a1, $a2 ) = partition( 30, $_ );
    my( $t1, $t2 ) = ( sum( @$a1), sum( @$a2 ) );
    print "\n@$a1 := ", $t1;
    print "@$a2 := ", $t2;
    print "Diff: ", abs( $t1 - $t2 );
}



sub partition {
    my( $limit, $aRef ) = @_;
    my @in = sort{ $a <=> $b } @$aRef;
    my $target = sum( @in ) >> 1;
    my( $best, @best ) = 9e99;
    my $soFar = 0;
    my @half;
    for( 1 .. $limit ) {
#        printf "%6d : [@half] [@in] [@best]\n", abs( $soFar - $target
+ ) if $V;

        $soFar += $in[ 0 ], push @half, shift @in while $soFar < $targ
+et;
        return( \@half, \@in ) if $soFar == $target;

        my $diff = abs( $soFar - $target );
        ( $best, @best ) = ( $diff, @half ) if $diff < $best;

        $soFar -= $half[ 0 ], push @in, shift @half while $soFar > $ta
+rget;
        return( \@half, \@in ) if $soFar == $target;

        $diff = abs( $soFar - $target );
        ( $best, @best ) = ( $diff, @half ) if $diff < $best;

        srand( $_ );
        shuffle @in;
    }
    my %seen; $seen{ $_ }++ for @best;
    return \@best, [ grep{ --$seen{ $_ } < 0 } @$aRef ];
}
[download]

Update: I know know why the problem didn't show up in my version of the script. As I mentioned, I'm using a custom shuffle routine, which does an in-place shuffle. The List::Util version of shuffle is not in-place, hence the last line of the for loop should be @in = shuffle @in; for use with List::Util, not shuffle @in; as for my version. I've update the code below.

I apologise. It is a legit bug. I'm amazed it hasn't shown up before and confused as to why it doesn't show up in my lightly modified version of the same script you posted, but...this fixes it. Till the next one....

sub partition {
    my( $limit, $aRef ) = @_;
    my @in = sort{ $a <=> $b } @$aRef;
    my $target = sum( @in ) >> 1;
    my( $best, @best ) = 9e99;
    my $soFar = 0;
    my @half;
    for( 1 .. $limit ) {
#        printf "%6d : [@half] [@in] [@best]\n", abs( $soFar - $target
+ );

        $soFar += $in[ 0 ], push @half, shift @in
            while @in > 1 and $soFar < $target;
        return( \@half, \@in ) if $soFar == $target;

        my $diff = abs( $soFar - $target );
        ( $best, @best ) = ( $diff, @half ) if $diff < $best;

        $soFar -= $half[ 0 ], push @in, shift @half
            while @half > 1 and $soFar > $target;
        return( \@half, \@in ) if $soFar == $target;

        $diff = abs( $soFar - $target );
        ( $best, @best ) = ( $diff, @half ) if $diff < $best;

        srand( $_ );
        @in = shuffle @in;
        ## shuffle @in; ## Only works for an inplace shuffle!
    }
    my %seen; $seen{ $_ }++ for @best;
    return \@best, [ grep{ --$seen{ $_ } < 0 } @$aRef ];
}
[download]

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."