Re: Divide array of integers into most similar value halves

How about...

@numbers = reverse sort @numbers
$target = sum(@numbers)/2
loop forever {
find largest $number in @numbers that is smaller than $target
exit loop if not found
add that number to @bucket
remove that number from @numbers
subtract that number from $target
}
return @bucket and @numbers

and in perl 5.10...

use List::Util qw(sum);
use List::MoreUtils qw(first_index);

#my @numbers = map { rand() * 100 } 1 .. 5;
my @numbers = (8,14,32,29);

my @b = split_evenly( \@numbers );

say "First container:  sum(@{$b[0]}) = ", sum @{$b[0]};
say "Second container: sum(@{$b[1]}) = ", sum @{$b[1]};

sub split_evenly {
    my @numbers = reverse sort { $a <=> $b } @{+shift};
    my $target = sum(@numbers) / 2;
    say "Target is $target";

    my @b;
    while ( 1 ) {
        my $index = first_index { $_ <= $target } @numbers;
        last if $index < 0;
        $target -= $numbers[$index];
        push @b, splice @numbers, $index, 1;
    }
    return \@b, \@numbers;
}
[download]

replace the says with print for perl < 5.10.

Tested, but not exhaustively. Use at your own risk. etc.

Update: changed the output so the lists are displayed.

Unless I state otherwise, all my code runs with strict and warnings

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 JadeNB (Chaplain) on Sep 01, 2008 at 22:05 UTC
Unfortunately, this algorithm can fail. I didn't turn up an example with small numbers after some thinking, so here's one that I stole from an article transitively linked by Skeeve: the set `{62, 83, 121, 281, 486, 734, 771, 854, 885, 1003}` has a perfect partition (namely, `{62, 83, 121, 486, 885, 1003}`), but the greedy algorithm that you suggest returns `{1003, 885, 734}`, which has a defect of 18 (not 32, I think, despite the article). The algorithm I used to find that match is based on my imperfect recall of the one from Dominus's book mentioned by moritz. I'm sure it can be made much more elegant (for example, by not hard-wiring `@list`; and, less trivially, by not passing in `$so_far_ref`—I was just using it to print the diagnostics), but I think that this works: Read more... (2 kB)	[reply] [d/l] [select]
Re^3: Divide array of integers into most similar value halves by FunkyMonk (Bishop) on Sep 01, 2008 at 22:29 UTC
I was aware that my "solution" wasn't perfect, but the OP suggested that near enough was good enough. Everything in life is a comprimise :-)	[reply]
Re^3: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 02, 2008 at 02:57 UTC
Thanks for noting. I'm still trying it out the first algorithm in my data. I believe is close enough for what I want. Of course I'm open to any improvements... Thanks a lot.	[reply]
Re^2: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 02, 2008 at 03:58 UTC
Hey FunkyMonk, sorry to bother you again, but I've been extensively testing the script you posted and works most of the time but fails in cases as: @array = (41,37,37,43) returning @array1=(43) @array2=(41,37,37) Any ideas? Thanks in advance Pepe	[reply]
Re^3: Divide array of integers into most similar value halves by FunkyMonk (Bishop) on Sep 02, 2008 at 16:40 UTC
Take a look at moritz's orginal reply and its followups. That's the difference between doing it correctly (their discussion) and an evil, dirty, quick hack (my version). It all depends with how bad "good enough" can be :) My program will never allow the first container to hold more than $target. All the other numbers go into the second. With (41,37,37,43) as input, 43 goes into the first container, and none of the other numbers will fit, so all the rest go into the second container. Tweaking the comparison in first_index will allow this dataset to be divided more evenly, but will produce worse solutions in some cases. For example, making this change `first_index { $_ <= $target*1.1 } # allow container to overflow by 10%` [download] produces (I changed the output format slightly): `Original numbers: (41 37 37 43) Target is 79 First container: sum(43 37) = 80 Second container: sum(41 37) = 78` [download] The code is fast, so there's nothing to stop you dividing your numbers twice using the untweaked and tweaked comparison and choosing the answer you like best. But, all that does is make a dirty, evil, quick hack dirtier, more evil and slower. You'll still be able to find cases where it fails. The only real solution is to do it properly. Unless I state otherwise, all my code runs with strict and warnings	[reply] [d/l] [select]
Re^4: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 02, 2008 at 17:58 UTC
Thanks FunkyMonk!!! I already fixed the problem (hopefully) by doing one more iteration of the loop and checking if the difference between subarrays were smaller. Your suggestion is maybe better in terms of time. I'm trying it now. It's a great script anyway. Thank's a lot. It's important for me to make this work, but not to spend days in the calculations.	[reply]
Re^2: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 01, 2008 at 20:50 UTC
So far works for me, I have to test it in 20.000 arrays, so I will write some code to prove that it works fine, but it seems to do pretty well. Thanks a lot It's been great help!!!!	[reply]