Re: 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

Comment on Re: Divide array of integers into most similar value halves Download Code

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]
Re^3: Divide array of integers into most similar value halves by bduggan (Pilgrim) on Sep 03, 2008 at 13:56 UTC
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]
Re^4: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 03, 2008 at 15:28 UTC
You're right bduggan, Although it may be close enough for me	[reply]
Re^4: Divide array of integers into most similar value halves by johndageek (Hermit) on Sep 04, 2008 at 13:34 UTC
Excellent point! Thanks! Enjoy! Dageek	[reply]
Re^4: Divide array of integers into most similar value halves by Anonymous Monk on Jan 07, 2009 at 15:09 UTC
	[reply]
Re^4: Divide array of integers into most similar value halves by Anonymous Monk on Jan 07, 2009 at 15:10 UTC
{ 2 } { 3 3 2 2 } { 3 2 } { 3 2 2 } { 2 2 } { 3 3 2 } { 10 4 4 } { 10 4 4 4 } { 10 4 4 4 } { 10 4 4 } Above are the possible solutions. allowable avg mismatch range was chosen 1	[reply]


Pathologically Eclectic Rubbish Lister
	PerlMonks