in reply to Divide array of integers into most similar value halves

Jsut my simple attempt: 
#!/usr/bin/perl
## arrays to test
#@aoi = (1,33,2,5,6,2,9999,1,555,333,654,8,1,234,0,765,2,3,446,753);
#@aoi = (1,33,2,5,6,2,999,1,555,333,654,8,1,234,0,765,2,3,446,753);
#@aoi = (1,1,33,2,5,6,2,999,1,555,333,654,8,1,234,0,765,2,3,446,753);
#@aoi = (1,1,33,2,5,6,2,999,8,1,555,333,654,8,1,234,0,765,2,3,446,753)
+;
@aoi = (2406,1,1,33,2,5,6,2,999,8,1,555,333,654,8,1,234,0,765,2,3,446,
+753);
# working variables
@arr1 = ();
$sum1 = 0;
@arr2=();
$sum2 = 0;
# sort list
@saoi =  sort { $a <=> $b} @aoi;
## start with highest value working downwards, pushing onto array cont
+aining
## the lowest sum. SHould give you the least available difference betw
+een array sums
for ($t=$#saoi;$t>-1;$t--){
  if ($sum2 > $sum1){
    $sum1 = $sum1 + $saoi[$t];
    push @arr1,$saoi[$t];
  }else{
    $sum2 = $sum2 + $saoi[$t];
    push @arr2,$saoi[$t];
  }
}
$diff = $sum2 - $sum1;
print "$sum2 -  $sum1 = $diff\n";

[download]

Enjoy!
Dageek

Replies are listed 'Best First'.
Re^2: Divide array of integers into most similar value halves
by Pepe (Sexton) on Sep 02, 2008 at 18:42 UTC
    Dageek,

    this is a great idea!!! I'm gonna try it.
    By adding the next value to the smallest group the result should be close to optimum.
    Also simple and fast

    Thanks a lot
    Pepe
[reply]
      It'll fail for e.g. (3,3,2,2,2) and other sets where the top two numbers are odd, the rest even, and the ideal split is even. (and other cases too, e.g. (10,10,4,4,4,4,4))
[reply]
        You're right bduggan,
        Although it may be close enough for me
[reply]
        Excellent point! Thanks!

        Enjoy!
        Dageek

[reply]
    		[reply]
    [reply]

    In Section Seekers of Perl Wisdom