Re^2: Divide array of integers into most similar value halves

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:

use List::Util qw/first sum/;
use strict;
use warnings 'all';

my @list = (62, 83, 121, 281, 486, 734, 771, 854, 885, 1003);
my $sum = sum(@list)/2;
print "Trying for $sum with possibilities @list\n";
my @match = sum_to($sum, [], \@list);
print @match ? "MATCH @match\n" : "No match\n";

sub sum_to {
        my ( $target, $so_far_ref, $possibilities_ref ) = @_;
        my @so_far = @$so_far_ref;
        my @possibilities = @$possibilities_ref;
        local $_;
        my $exact = first { $_ == $target } @possibilities;
        return $exact if $exact;
        local $_;
        my @indices = grep { $possibilities[$_] <= $target } 0 .. $#po
+ssibilities;
        unless ( @indices ) {
                print "That branch didn't work.\n";
                return;
        }
        my ( $sum, $try, @match );
        INDEX:
        for my $index ( @indices ) {
                my @internal_possibilities = @possibilities;
                my @internal_so_far = @so_far;
                $try = splice @internal_possibilities, $index, 1;
                push @internal_so_far, $try;
                print "Guessed @internal_so_far; recursively trying fo
+r ", $target - $try, " with possibilities @internal_possibilities\n";
                @match = sum_to($target - $try, \@internal_so_far, \@i
+nternal_possibilities) and last INDEX;
        }
        return @match ? ( $try, @match ) : ();
}
[download]

Comment on Re^2: Divide array of integers into most similar value halves Select or Download Code

Replies are listed 'Best First'.
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]