in reply to Re^10: Divide array of integers into most similar value halves
in thread Divide array of integers into most similar value halves

Okay. Try this version.

  1. It (finally) corrects the duplicates problem (with many thanks to betterworld++).
  2. It will find the optimum solution much more often with far fewer iterations.

    In most tests I've run, a limit of 10* the number of elements finds the optimum even for large arrsys of widely spaced numbers.

    Most of my tests having been run using a custom shuffle that uses Math::Random::MT, but that was mostly to achieve repeatability. I see no reason that you will not see similar results using your native rand() and List::Util::shuffle(). 

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]
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."

Replies are listed 'Best First'.
Re^12: Divide array of integers into most similar value halves
by Pepe (Sexton) on Sep 04, 2008 at 21:02 UTC
    It doesn't separate arrays like:

    @array=(11,39,62);

    returns that same array and an empty one...
    Sorry.
[reply]
[reply]
[d/l]

      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".

      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.
[reply]
        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]
[reply]
[d/l]

In Section Seekers of Perl Wisdom