Re: Divide an array into 2 subsets to verify their sum is equal or not.

Update:

There's a bug in this code (see ++roboticus' response). Don't use this until I fix it which, unfortunately, I don't have time to do immediately. :-(

Update2: Original solution substantially rewritten! It had various problems:

Failed with data like [ 7, 5, 3, 3] (see ++roboticus' response) and [ 8, 4, 4, 7, 6, 3 ] (see ++hdb's explanation).
Contained some fairly crappy code (see ++BrowserUk's questions).
Didn't test edge/corner cases such as empty array, single element array, arrays containing only zeros.

Here's the original code I posted:

Here's my take on a solution. I added some additional test data (one copied from choroba's solution).

#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{sum};

my @test_arrays = ( 
    [1, 3, 8, 4], 
    [1, 6, 2], 
    [1, 3, 5, 7], 
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
);  

check_arrays($_) for @test_arrays;

sub check_arrays {
    my @full_array = @{shift()};
    print "Checking: (", join(", " => @full_array), ")";
    my $sum = sum @full_array;

    if ($sum % 2) {
        print "\tSubsets not equal";
        return;
    }   

    my $half = $sum / 2;
    my (@a1, @a2);

    for (sort { $b <=> $a } @full_array) {
        push @{(sum(@a1) || 0) + $_ <= $half ? \@a1 : \@a2} => $_;
    }

    print "\tSubsets: (", join(", " => sort { $a <=> $b } @a1),
            ") and (", join(", " => sort { $a <=> $b } @a2), ")";
    print "\tSubset sum = $half";
}
[download]

Output:

$ pm_split_equal_sums.pl
Checking: (1, 3, 8, 4)
    Subsets: (8) and (1, 3, 4)
    Subset sum = 8
Checking: (1, 6, 2)
    Subsets not equal
Checking: (1, 3, 5, 7)
    Subsets: (1, 7) and (3, 5)
    Subset sum = 8
Checking: (4, 3, 2, 2, 1)
    Subsets: (2, 4) and (1, 2, 3)
    Subset sum = 6
Checking: (4, 3, 2, 2, 2, 2, 1)
    Subsets: (1, 3, 4) and (2, 2, 2, 2)
    Subset sum = 8
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
    Subsets: (1, 2, 8, 9) and (4, 5, 5, 6)
    Subset sum = 20
[download]

Here's the rewrite:

#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{sum};
use Test::More;

my @test_equal_subsets = (
    [1, 3, 8, 4],
    [1, 3, 5, 7],
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
    [1, 1],
    [2, 2],
    [],
    [0],
    [0, 0],
    [0, 0, 0],
    [0, 0, 0, 0],
);

my @test_unequal_subsets = (
    [1, 6, 2],
    [7, 5, 3, 3],
    [8, 4, 4, 7, 6, 3],
    [0, 1],
    [1, 2],
    [1],
    [2],
);

plan tests => scalar @test_equal_subsets + scalar @test_unequal_subset
+s;

for (@test_equal_subsets) {
    is(check_arrays($_), 1, 'Expecting equal subsets.');
}

for (@test_unequal_subsets) {
    is(check_arrays($_), 0, 'Not expecting equal subsets.');
}

sub check_arrays {
    my $full_array = shift;

    print "Checking: (", join(", " => @$full_array), ")";

    if (! grep { $_ } @$full_array) {
        print "\tSubsets: (", join(", " => @$full_array), ') and ()';
        print "\tSubset sum = 0";
        return 1;
    }

    my $full_sum = sum @$full_array;

    if ($full_sum % 2) { 
        print "\tSubsets not equal.";
        return 0;
    }

    my $half_sum = $full_sum / 2;
    my (@a1, @a2);
    my $a1_total = 0;

    for (sort { $b <=> $a } @$full_array) {
        if ($a1_total + $_ <= $half_sum) {
            push @a1, $_;
            $a1_total += $_;
        }
        else {
            push @a2, $_;
        }
    }

    if ($a1_total == $half_sum) {
        print "\tSubsets: (", join(", " => sort { $a <=> $b } @a1),
                ") and (", join(", " => sort { $a <=> $b } @a2), ")";
        print "\tSubset sum = $half_sum";
        return 1;
    }
    else {
        print "\tSubsets not equal.";
        return 0
    }
}
[download]

Here's prove output:

$ prove pm_split_equal_sums.pl
pm_split_equal_sums.pl .. ok     
All tests successful.
Files=1, Tests=19,  0 wallclock secs ( 0.03 usr  0.01 sys +  0.02 cusr
+  0.00 csys =  0.06 CPU)
Result: PASS
[download]

Here's the full output:

$ pm_split_equal_sums.pl
1..19
Checking: (1, 3, 8, 4)
    Subsets: (8) and (1, 3, 4)
    Subset sum = 8
ok 1 - Expecting equal subsets.
Checking: (1, 3, 5, 7)
    Subsets: (1, 7) and (3, 5)
    Subset sum = 8
ok 2 - Expecting equal subsets.
Checking: (4, 3, 2, 2, 1)
    Subsets: (2, 4) and (1, 2, 3)
    Subset sum = 6
ok 3 - Expecting equal subsets.
Checking: (4, 3, 2, 2, 2, 2, 1)
    Subsets: (1, 3, 4) and (2, 2, 2, 2)
    Subset sum = 8
ok 4 - Expecting equal subsets.
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
    Subsets: (1, 2, 8, 9) and (4, 5, 5, 6)
    Subset sum = 20
ok 5 - Expecting equal subsets.
Checking: (1, 1)
    Subsets: (1) and (1)
    Subset sum = 1
ok 6 - Expecting equal subsets.
Checking: (2, 2)
    Subsets: (2) and (2)
    Subset sum = 2
ok 7 - Expecting equal subsets.
Checking: ()
    Subsets: () and ()
    Subset sum = 0
ok 8 - Expecting equal subsets.
Checking: (0)
    Subsets: (0) and ()
    Subset sum = 0
ok 9 - Expecting equal subsets.
Checking: (0, 0)
    Subsets: (0, 0) and ()
    Subset sum = 0
ok 10 - Expecting equal subsets.
Checking: (0, 0, 0)
    Subsets: (0, 0, 0) and ()
    Subset sum = 0
ok 11 - Expecting equal subsets.
Checking: (0, 0, 0, 0)
    Subsets: (0, 0, 0, 0) and ()
    Subset sum = 0
ok 12 - Expecting equal subsets.
Checking: (1, 6, 2)
    Subsets not equal.
ok 13 - Not expecting equal subsets.
Checking: (7, 5, 3, 3)
    Subsets not equal.
ok 14 - Not expecting equal subsets.
Checking: (8, 4, 4, 7, 6, 3)
    Subsets not equal.
ok 15 - Not expecting equal subsets.
Checking: (0, 1)
    Subsets not equal.
ok 16 - Not expecting equal subsets.
Checking: (1, 2)
    Subsets not equal.
ok 17 - Not expecting equal subsets.
Checking: (1)
    Subsets not equal.
ok 18 - Not expecting equal subsets.
Checking: (2)
    Subsets not equal.
ok 19 - Not expecting equal subsets.
[download]

Update3: Fixed a bug and added some features:

Fixed problem reported by ++LanX.
Added in the same timing metrics used by BrowserUk for comparison.
Added volume testing.
Added options: --tm|test_more=0|1 switch Test::More tests off/on (def=1); --th|time_hires=0|1 switch Time::HiRes metrics off/on (def=1); --vt|volume_tests=0|1 switch volume tests off/on (def=0); --vpm|volume_power_max=1..N create arrays with 10**1 to 10**N elements for volume testing (def=3); --array_limit=0..N only show the first/last N elements of long arrays (def=3).

Here's pm_split_equal_sums.pl:

#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{sum};
use Test::More;
use Time::HiRes qw[ time ];
use Getopt::Long;

my %opt = (
    test_more   => 1,
    time_hires  => 1,
    volume_tests        => 0,
    volume_power_max    => 3,
    array_limit => 3,
);

GetOptions(map {
    join('|' => @{[join '' => /(?>^|_)([a-z])/gi]}, $_) . ':i' => \$op
+t{$_}
} keys %opt);

my $test_equal_subsets = [
    [1, 3, 8, 4],
    [1, 3, 5, 7],
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
    [8, 4, 4, 7, 6, 3],
    [1, 1],
    [2, 2],
    [],
    [0],
    [0, 0],
    [0, 0, 0],
    [0, 0, 0, 0],
];

my $test_unequal_subsets = [
    [1, 6, 2],
    [7, 5, 3, 3],
    [1, 2 ,3, 7],
    [0, 1],
    [1, 2],
    [1],
    [2],
    [8, 1, 2, 3],
];

if ($opt{volume_tests}) {
    for (1 .. $opt{volume_power_max}) {
        my @volume = (1 .. 10**$_ / 2) x 2;
        push @$test_equal_subsets, [@volume];
        push @volume, 10**(2 * $_);
        push @$test_unequal_subsets, [@volume];
    }
}

if ($opt{test_more}) {
    plan tests => scalar @$test_equal_subsets + scalar @$test_unequal_
+subsets;
}

my @expectations = ('Not expecting equal subsets.', 'Expecting equal s
+ubsets.');
my @subsets_data = ([$test_unequal_subsets, 0, 0], [$test_equal_subset
+s, 1, 1]);

for (@subsets_data) {
    my ($subsets, $expect_code, $expect_name_index) = @$_;
    my $expect_name = $expectations[$expect_name_index];

    for (@$subsets) {
        my $start = time if $opt{time_hires};

        if ($opt{test_more}) {
            is(check_arrays($_), $expect_code, $expect_name);
        }
        else {
            check_arrays($_);
        }

        printf "Took %f seconds\n", time() - $start if $opt{time_hires
+};
    }
}

sub check_arrays {
    my $full_array = shift;

    print 'Checking: (', array_string($full_array), ')';

    if (! grep { $_ } @$full_array) {
        print "\tSubsets: (", array_string($full_array), ') and ()';
        print "\tSubset sum = 0";
        return 1;
    }

    my $full_sum = sum @$full_array;

    if ($full_sum % 2) {
        print "\tSubsets not equal.";
        return 0;
    }

    my $half_sum = $full_sum / 2;
    my @sorted_array = sort { $b <=> $a } @$full_array;

    if ($sorted_array[0] > $half_sum) {
        print "\tSubsets not equal.";
        return 0;
    }

    my (@a1, @a2);
    my $total = 0;

    while (@sorted_array) {
        $total = 0;
        for (@sorted_array) {
            if ($total + $_ <= $half_sum) {
                push @a1, $_;
                $total += $_;
            }
        }

        if ($total == $half_sum) {
            push @a2, @sorted_array;
            last;
        }
        else {
            push @a2, shift @sorted_array or last;
            $total = 0;
        }
    }

    if ($total == $half_sum) {
        print "\tSubsets: (", array_string([sort { $a <=> $b } @a2]), 
+')';
        print "\t     and (", array_string([sort { $a <=> $b } @a2]), 
+')';
        print "\tSubset sum = $half_sum";
        return 1;
    }
    else {
        print "\tSubsets not equal.";
        return 0
    }
}

sub array_string {
    my $array = shift;

    return join(', ' => @$array > 3 * $opt{array_limit}
        ? ( @$array[0 .. $opt{array_limit} - 1],
            " ... [snip: @{[@$array - 2 * $opt{array_limit}]} elements
+] ...",
            @$array[@$array - $opt{array_limit} .. $#$array] )
        : @$array);
}
[download]

Sample run:

$ pm_split_equal_sums.pl --tm=1 --th=1 --vt=1 --vpm=5 --al=3
1..31
Checking: (1, 6, 2)
    Subsets not equal.
ok 1 - Not expecting equal subsets.
Took 0.000307 seconds
Checking: (7, 5, 3, 3)
    Subsets not equal.
ok 2 - Not expecting equal subsets.
Took 0.000197 seconds
Checking: (1, 2, 3, 7)
    Subsets not equal.
ok 3 - Not expecting equal subsets.
Took 0.000180 seconds
Checking: (0, 1)
    Subsets not equal.
ok 4 - Not expecting equal subsets.
Took 0.000166 seconds
Checking: (1, 2)
    Subsets not equal.
ok 5 - Not expecting equal subsets.
Took 0.000165 seconds
Checking: (1)
    Subsets not equal.
ok 6 - Not expecting equal subsets.
Took 0.000164 seconds
Checking: (2)
    Subsets not equal.
ok 7 - Not expecting equal subsets.
Took 0.000168 seconds
Checking: (8, 1, 2, 3)
    Subsets not equal.
ok 8 - Not expecting equal subsets.
Took 0.000170 seconds
Checking: (1, 2, 3,  ... [snip: 5 elements] ..., 4, 5, 100)
    Subsets not equal.
ok 9 - Not expecting equal subsets.
Took 0.000183 seconds
Checking: (1, 2, 3,  ... [snip: 95 elements] ..., 49, 50, 10000)
    Subsets not equal.
ok 10 - Not expecting equal subsets.
Took 0.000191 seconds
Checking: (1, 2, 3,  ... [snip: 995 elements] ..., 499, 500, 1000000)
    Subsets not equal.
ok 11 - Not expecting equal subsets.
Took 0.000313 seconds
Checking: (1, 2, 3,  ... [snip: 9995 elements] ..., 4999, 5000, 100000
+000)
    Subsets not equal.
ok 12 - Not expecting equal subsets.
Took 0.001494 seconds
Checking: (1, 2, 3,  ... [snip: 99995 elements] ..., 49999, 50000, 100
+00000000)
    Subsets not equal.
ok 13 - Not expecting equal subsets.
Took 0.013494 seconds
Checking: (1, 3, 8, 4)
    Subsets: (1, 3, 4, 8)
         and (1, 3, 4, 8)
    Subset sum = 8
ok 14 - Expecting equal subsets.
Took 0.000205 seconds
Checking: (1, 3, 5, 7)
    Subsets: (1, 3, 5, 7)
         and (1, 3, 5, 7)
    Subset sum = 8
ok 15 - Expecting equal subsets.
Took 0.000195 seconds
Checking: (4, 3, 2, 2, 1)
    Subsets: (1, 2, 2, 3, 4)
         and (1, 2, 2, 3, 4)
    Subset sum = 6
ok 16 - Expecting equal subsets.
Took 0.000205 seconds
Checking: (4, 3, 2, 2, 2, 2, 1)
    Subsets: (1, 2, 2, 2, 2, 3, 4)
         and (1, 2, 2, 2, 2, 3, 4)
    Subset sum = 8
ok 17 - Expecting equal subsets.
Took 0.000201 seconds
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
    Subsets: (1, 2, 4, 5, 5, 6, 8, 9)
         and (1, 2, 4, 5, 5, 6, 8, 9)
    Subset sum = 20
ok 18 - Expecting equal subsets.
Took 0.000202 seconds
Checking: (8, 4, 4, 7, 6, 3)
    Subsets: (3, 4, 4, 6, 7, 8)
         and (3, 4, 4, 6, 7, 8)
    Subset sum = 16
ok 19 - Expecting equal subsets.
Took 0.000199 seconds
Checking: (1, 1)
    Subsets: (1, 1)
         and (1, 1)
    Subset sum = 1
ok 20 - Expecting equal subsets.
Took 0.000188 seconds
Checking: (2, 2)
    Subsets: (2, 2)
         and (2, 2)
    Subset sum = 2
ok 21 - Expecting equal subsets.
Took 0.000186 seconds
Checking: ()
    Subsets: () and ()
    Subset sum = 0
ok 22 - Expecting equal subsets.
Took 0.000167 seconds
Checking: (0)
    Subsets: (0) and ()
    Subset sum = 0
ok 23 - Expecting equal subsets.
Took 0.000166 seconds
Checking: (0, 0)
    Subsets: (0, 0) and ()
    Subset sum = 0
ok 24 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0, 0, 0)
    Subsets: (0, 0, 0) and ()
    Subset sum = 0
ok 25 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0, 0, 0, 0)
    Subsets: (0, 0, 0, 0) and ()
    Subset sum = 0
ok 26 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (1, 2, 3,  ... [snip: 4 elements] ..., 3, 4, 5)
    Subsets: (1, 1, 2,  ... [snip: 4 elements] ..., 4, 5, 5)
         and (1, 1, 2,  ... [snip: 4 elements] ..., 4, 5, 5)
    Subset sum = 15
ok 27 - Expecting equal subsets.
Took 0.000211 seconds
Checking: (1, 2, 3,  ... [snip: 94 elements] ..., 48, 49, 50)
    Subsets: (1, 1, 2,  ... [snip: 94 elements] ..., 49, 50, 50)
         and (1, 1, 2,  ... [snip: 94 elements] ..., 49, 50, 50)
    Subset sum = 1275
ok 28 - Expecting equal subsets.
Took 0.000269 seconds
Checking: (1, 2, 3,  ... [snip: 994 elements] ..., 498, 499, 500)
    Subsets: (1, 1, 2,  ... [snip: 994 elements] ..., 499, 500, 500)
         and (1, 1, 2,  ... [snip: 994 elements] ..., 499, 500, 500)
    Subset sum = 125250
ok 29 - Expecting equal subsets.
Took 0.000762 seconds
Checking: (1, 2, 3,  ... [snip: 9994 elements] ..., 4998, 4999, 5000)
    Subsets: (1, 1, 2,  ... [snip: 9994 elements] ..., 4999, 5000, 500
+0)
         and (1, 1, 2,  ... [snip: 9994 elements] ..., 4999, 5000, 500
+0)
    Subset sum = 12502500
ok 30 - Expecting equal subsets.
Took 0.005873 seconds
Checking: (1, 2, 3,  ... [snip: 99994 elements] ..., 49998, 49999, 500
+00)
    Subsets: (1, 1, 2,  ... [snip: 99994 elements] ..., 49999, 50000, 
+50000)
         and (1, 1, 2,  ... [snip: 99994 elements] ..., 49999, 50000, 
+50000)
    Subset sum = 1250025000
ok 31 - Expecting equal subsets.
Took 0.060788 seconds
[download]

Timing metrics are probably best run without the overhead of Test::More:

$ pm_split_equal_sums.pl --tm=0 --th=1 --vt=1 --vpm=5 --al=3
Checking: (1, 6, 2)
    Subsets not equal.
Took 0.000059 seconds
Checking: (7, 5, 3, 3)
    Subsets not equal.
Took 0.000036 seconds
Checking: (1, 2, 3, 7)
    Subsets not equal.
Took 0.000010 seconds
Checking: (0, 1)
    Subsets not equal.
Took 0.000009 seconds
Checking: (1, 2)
    Subsets not equal.
Took 0.000008 seconds
Checking: (1)
    Subsets not equal.
Took 0.000008 seconds
Checking: (2)
    Subsets not equal.
Took 0.000011 seconds
Checking: (8, 1, 2, 3)
    Subsets not equal.
Took 0.000012 seconds
Checking: (1, 2, 3,  ... [snip: 5 elements] ..., 4, 5, 100)
    Subsets not equal.
Took 0.000026 seconds
Checking: (1, 2, 3,  ... [snip: 95 elements] ..., 49, 50, 10000)
    Subsets not equal.
Took 0.000031 seconds
Checking: (1, 2, 3,  ... [snip: 995 elements] ..., 499, 500, 1000000)
    Subsets not equal.
Took 0.000150 seconds
Checking: (1, 2, 3,  ... [snip: 9995 elements] ..., 4999, 5000, 100000
+000)
    Subsets not equal.
Took 0.001309 seconds
Checking: (1, 2, 3,  ... [snip: 99995 elements] ..., 49999, 50000, 100
+00000000)
    Subsets not equal.
Took 0.012939 seconds
Checking: (1, 3, 8, 4)
    Subsets: (1, 3, 4, 8)
         and (1, 3, 4, 8)
    Subset sum = 8
Took 0.000054 seconds
Checking: (1, 3, 5, 7)
    Subsets: (1, 3, 5, 7)
         and (1, 3, 5, 7)
    Subset sum = 8
Took 0.000029 seconds
Checking: (4, 3, 2, 2, 1)
    Subsets: (1, 2, 2, 3, 4)
         and (1, 2, 2, 3, 4)
    Subset sum = 6
Took 0.000032 seconds
Checking: (4, 3, 2, 2, 2, 2, 1)
    Subsets: (1, 2, 2, 2, 2, 3, 4)
         and (1, 2, 2, 2, 2, 3, 4)
    Subset sum = 8
Took 0.000035 seconds
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
    Subsets: (1, 2, 4, 5, 5, 6, 8, 9)
         and (1, 2, 4, 5, 5, 6, 8, 9)
    Subset sum = 20
Took 0.000038 seconds
Checking: (8, 4, 4, 7, 6, 3)
    Subsets: (3, 4, 4, 6, 7, 8)
         and (3, 4, 4, 6, 7, 8)
    Subset sum = 16
Took 0.000036 seconds
Checking: (1, 1)
    Subsets: (1, 1)
         and (1, 1)
    Subset sum = 1
Took 0.000024 seconds
Checking: (2, 2)
    Subsets: (2, 2)
         and (2, 2)
    Subset sum = 2
Took 0.000025 seconds
Checking: ()
    Subsets: () and ()
    Subset sum = 0
Took 0.000011 seconds
Checking: (0)
    Subsets: (0) and ()
    Subset sum = 0
Took 0.000011 seconds
Checking: (0, 0)
    Subsets: (0, 0) and ()
    Subset sum = 0
Took 0.000011 seconds
Checking: (0, 0, 0)
    Subsets: (0, 0, 0) and ()
    Subset sum = 0
Took 0.000011 seconds
Checking: (0, 0, 0, 0)
    Subsets: (0, 0, 0, 0) and ()
    Subset sum = 0
Took 0.000011 seconds
Checking: (1, 2, 3,  ... [snip: 4 elements] ..., 3, 4, 5)
    Subsets: (1, 1, 2,  ... [snip: 4 elements] ..., 4, 5, 5)
         and (1, 1, 2,  ... [snip: 4 elements] ..., 4, 5, 5)
    Subset sum = 15
Took 0.000050 seconds
Checking: (1, 2, 3,  ... [snip: 94 elements] ..., 48, 49, 50)
    Subsets: (1, 1, 2,  ... [snip: 94 elements] ..., 49, 50, 50)
         and (1, 1, 2,  ... [snip: 94 elements] ..., 49, 50, 50)
    Subset sum = 1275
Took 0.000111 seconds
Checking: (1, 2, 3,  ... [snip: 994 elements] ..., 498, 499, 500)
    Subsets: (1, 1, 2,  ... [snip: 994 elements] ..., 499, 500, 500)
         and (1, 1, 2,  ... [snip: 994 elements] ..., 499, 500, 500)
    Subset sum = 125250
Took 0.000599 seconds
Checking: (1, 2, 3,  ... [snip: 9994 elements] ..., 4998, 4999, 5000)
    Subsets: (1, 1, 2,  ... [snip: 9994 elements] ..., 4999, 5000, 500
+0)
         and (1, 1, 2,  ... [snip: 9994 elements] ..., 4999, 5000, 500
+0)
    Subset sum = 12502500
Took 0.005701 seconds
Checking: (1, 2, 3,  ... [snip: 99994 elements] ..., 49998, 49999, 500
+00)
    Subsets: (1, 1, 2,  ... [snip: 99994 elements] ..., 49999, 50000, 
+50000)
         and (1, 1, 2,  ... [snip: 99994 elements] ..., 49999, 50000, 
+50000)
    Subset sum = 1250025000
Took 0.060971 seconds
[download]

Update4: Fixed some bugs and changed volume testing.

Display issue with subset output. Duplicate data due to "@a2 ... @a2" not being "@a1 ... @a2". - FIXED.
while loop in check_arrays() had flaws. This has been pretty much rewritten. - FIXED.
Volume testing was decimal-based, now it's octal-based. Previously, --volume_power_max=3 [or --vpm=3] created arrays of up to 10**3 (1,000) elements; now, the value is 8**3 (512) elements. Decimal-based was a bad choice as neither 1 .. 10 nor 1 .. 100 can be split into two equal portions.
Added a few more tests.

Here's Update4's version of pm_split_equal_sums.pl:

#!/usr/bin/env perl -l

use strict;
use warnings;

use List::Util qw{first sum};
use Test::More;
use Time::HiRes qw{time};
use Getopt::Long;

my %opt = (
    test_more   => 1,
    time_hires  => 1,
    volume_tests        => 0,
    volume_power_max    => 3,
    array_limit => 3,
);

GetOptions(map {
    join('|' => @{[join '' => /(?>^|_)([a-z])/gi]}, $_) . ':i' => \$op
+t{$_}
} keys %opt);

my $test_equal_subsets = [
    [1, 3, 8, 4],
    [1, 3, 5, 7],
    [4, 3, 2, 2, 1],
    [4, 3, 2, 2, 2, 2, 1],
    [5, 5, 4, 6, 2, 8, 1, 9],
    [8, 4, 4, 7, 6, 3],
    [1, 1],
    [2, 2],
    [],
    [0],
    [0, 0],
    [0, 0, 0],
    [0, 0, 0, 0],
    [ (1) x 100 ],
    [ 1 .. 1000 ],
];

my $test_unequal_subsets = [
    [1, 6, 2],
    [7, 5, 3, 3],
    [1, 2 ,3, 7],
    [0, 1],
    [1, 2],
    [1],
    [2],
    [8, 1, 2, 3],
    [ 1 .. 10 ],
    [ 1 .. 100 ],
];

if ($opt{volume_tests}) {
    for (1 .. $opt{volume_power_max}) {
        my @volume = map { (($_), ($_)) } 1 .. 8**$_ / 2;
        push @$test_equal_subsets, [@volume];
        push @$test_unequal_subsets, [@volume, 8**(2 * $_)];
    }
}

if ($opt{test_more}) {
    plan tests => scalar @$test_equal_subsets + scalar @$test_unequal_
+subsets;
}

my @expectations = ('Not expecting equal subsets.', 'Expecting equal s
+ubsets.');
my @subsets_data = ([$test_unequal_subsets, 0, 0], [$test_equal_subset
+s, 1, 1]);

for (@subsets_data) {
    my ($subsets, $expect_code, $expect_name_index) = @$_;
    my $expect_name = $expectations[$expect_name_index];

    for (@$subsets) {
        my $start = time if $opt{time_hires};

        if ($opt{test_more}) {
            is(check_arrays($_), $expect_code, $expect_name);
        }
        else {
            check_arrays($_);
        }

        printf "Took %f seconds\n", time() - $start if $opt{time_hires
+};
    }
}

sub check_arrays {
    my $full_array = shift;

    print 'Checking: (', array_string($full_array), ')';

    if (! grep { $_ } @$full_array) {
        print "\tSubsets: (", array_string($full_array), ') and ()';
        print "\tSubset sum = 0";
        return 1;
    }

    my $full_sum = sum @$full_array;

    if ($full_sum % 2) {
        print "\tSubsets not equal: sum of starting array is odd ($ful
+l_sum).";
        return 0;
    }

    my $half_sum = $full_sum / 2;
    my @sorted_array = sort { $b % 2 <=> $a % 2 || $b <=> $a } @$full_
+array;

    if (my $big = first { $_ > $half_sum } @sorted_array) {
        print "\tSubsets not equal: element ($big) larger than sum of 
+rest.";
        return 0;
    }

    my (@a1, @a2);
    my $total = 0;

    while (@sorted_array) {
        push @a1, shift @sorted_array;
        $total += $a1[$#a1];

        @sorted_array = map { $total + $_ <= $half_sum
            ? do { push @a1, $_; $total += $_; () } : $_
        } @sorted_array;

        if ($total == $half_sum) {
            (@a2, @sorted_array) = (@a2, @sorted_array);
        }
        else {
            push @a2, pop @a1 if @a1;
        }
    }

    if ($total == $half_sum) {
        print "\tSubsets: (", array_string([sort { $a <=> $b } @a1]), 
+')';
        print "\t     and (", array_string([sort { $a <=> $b } @a2]), 
+')';
        print "\tSubset sum = $half_sum";
        return 1;
    }
    else {
        print "\tSubsets not equal: no solution found.";
        return 0
    }
}

sub array_string {
    my $array = shift;

    return join(', ' => @$array > 3 * $opt{array_limit}
        ? ( @$array[0 .. $opt{array_limit} - 1],
            " ... [snip: @{[@$array - 2 * $opt{array_limit}]} elements
+] ...",
            @$array[@$array - $opt{array_limit} .. $#$array] )
        : @$array);
}
[download]

Here's a test run. Note that this uses --vpm=8 and final volume test "Took 89.489836 seconds" — you might want to start with a lower value.

$ pm_split_equal_sums.pl --tm=1 --th=1 --vt=1 --vpm=8 --al=3
1..41
Checking: (1, 6, 2)
    Subsets not equal: sum of starting array is odd (9).
ok 1 - Not expecting equal subsets.
Took 0.000318 seconds
Checking: (7, 5, 3, 3)
    Subsets not equal: no solution found.
ok 2 - Not expecting equal subsets.
Took 0.000233 seconds
Checking: (1, 2, 3, 7)
    Subsets not equal: sum of starting array is odd (13).
ok 3 - Not expecting equal subsets.
Took 0.000169 seconds
Checking: (0, 1)
    Subsets not equal: sum of starting array is odd (1).
ok 4 - Not expecting equal subsets.
Took 0.000165 seconds
Checking: (1, 2)
    Subsets not equal: sum of starting array is odd (3).
ok 5 - Not expecting equal subsets.
Took 0.000167 seconds
Checking: (1)
    Subsets not equal: sum of starting array is odd (1).
ok 6 - Not expecting equal subsets.
Took 0.000165 seconds
Checking: (2)
    Subsets not equal: element (2) larger than sum of rest.
ok 7 - Not expecting equal subsets.
Took 0.000177 seconds
Checking: (8, 1, 2, 3)
    Subsets not equal: element (8) larger than sum of rest.
ok 8 - Not expecting equal subsets.
Took 0.000179 seconds
Checking: (1, 2, 3,  ... [snip: 4 elements] ..., 8, 9, 10)
    Subsets not equal: sum of starting array is odd (55).
ok 9 - Not expecting equal subsets.
Took 0.000179 seconds
Checking: (1, 2, 3,  ... [snip: 94 elements] ..., 98, 99, 100)
    Subsets not equal: no solution found.
ok 10 - Not expecting equal subsets.
Took 0.000817 seconds
Checking: (1, 1, 2, 2, 3, 3, 4, 4, 64)
    Subsets not equal: element (64) larger than sum of rest.
ok 11 - Not expecting equal subsets.
Took 0.000193 seconds
Checking: (1, 1, 2,  ... [snip: 59 elements] ..., 32, 32, 4096)
    Subsets not equal: element (4096) larger than sum of rest.
ok 12 - Not expecting equal subsets.
Took 0.000379 seconds
Checking: (1, 1, 2,  ... [snip: 507 elements] ..., 256, 256, 262144)
    Subsets not equal: element (262144) larger than sum of rest.
ok 13 - Not expecting equal subsets.
Took 0.000769 seconds
Checking: (1, 1, 2,  ... [snip: 4091 elements] ..., 2048, 2048, 167772
+16)
    Subsets not equal: element (16777216) larger than sum of rest.
ok 14 - Not expecting equal subsets.
Took 0.004773 seconds
Checking: (1, 1, 2,  ... [snip: 32763 elements] ..., 16384, 16384, 107
+3741824)
    Subsets not equal: element (1073741824) larger than sum of rest.
ok 15 - Not expecting equal subsets.
Took 0.035878 seconds
Checking: (1, 1, 2,  ... [snip: 262139 elements] ..., 131072, 131072, 
+68719476736)
    Subsets not equal: element (68719476736) larger than sum of rest.
ok 16 - Not expecting equal subsets.
Took 0.294454 seconds
Checking: (1, 1, 2,  ... [snip: 2097147 elements] ..., 1048576, 104857
+6, 4398046511104)
    Subsets not equal: element (4398046511104) larger than sum of rest
+.
ok 17 - Not expecting equal subsets.
Took 2.395664 seconds
Checking: (1, 1, 2,  ... [snip: 16777211 elements] ..., 8388608, 83886
+08, 281474976710656)
    Subsets not equal: element (281474976710656) larger than sum of re
+st.
ok 18 - Not expecting equal subsets.
Took 19.422507 seconds
Checking: (1, 3, 8, 4)
    Subsets: (1, 3, 4)
         and (8)
    Subset sum = 8
ok 19 - Expecting equal subsets.
Took 0.000223 seconds
Checking: (1, 3, 5, 7)
    Subsets: (1, 7)
         and (3, 5)
    Subset sum = 8
ok 20 - Expecting equal subsets.
Took 0.000201 seconds
Checking: (4, 3, 2, 2, 1)
    Subsets: (1, 2, 3)
         and (2, 4)
    Subset sum = 6
ok 21 - Expecting equal subsets.
Took 0.000203 seconds
Checking: (4, 3, 2, 2, 2, 2, 1)
    Subsets: (1, 3, 4)
         and (2, 2, 2, 2)
    Subset sum = 8
ok 22 - Expecting equal subsets.
Took 0.000208 seconds
Checking: (5, 5, 4, 6, 2, 8, 1, 9)
    Subsets: (1, 5, 5, 9)
         and (2, 4, 6, 8)
    Subset sum = 20
ok 23 - Expecting equal subsets.
Took 0.000209 seconds
Checking: (8, 4, 4, 7, 6, 3)
    Subsets: (3, 6, 7)
         and (4, 4, 8)
    Subset sum = 16
ok 24 - Expecting equal subsets.
Took 0.000206 seconds
Checking: (1, 1)
    Subsets: (1)
         and (1)
    Subset sum = 1
ok 25 - Expecting equal subsets.
Took 0.000197 seconds
Checking: (2, 2)
    Subsets: (2)
         and (2)
    Subset sum = 2
ok 26 - Expecting equal subsets.
Took 0.000195 seconds
Checking: ()
    Subsets: () and ()
    Subset sum = 0
ok 27 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0)
    Subsets: (0) and ()
    Subset sum = 0
ok 28 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0, 0)
    Subsets: (0, 0) and ()
    Subset sum = 0
ok 29 - Expecting equal subsets.
Took 0.000168 seconds
Checking: (0, 0, 0)
    Subsets: (0, 0, 0) and ()
    Subset sum = 0
ok 30 - Expecting equal subsets.
Took 0.000170 seconds
Checking: (0, 0, 0, 0)
    Subsets: (0, 0, 0, 0) and ()
    Subset sum = 0
ok 31 - Expecting equal subsets.
Took 0.000181 seconds
Checking: (1, 1, 1,  ... [snip: 94 elements] ..., 1, 1, 1)
    Subsets: (1, 1, 1,  ... [snip: 44 elements] ..., 1, 1, 1)
         and (1, 1, 1,  ... [snip: 44 elements] ..., 1, 1, 1)
    Subset sum = 50
ok 32 - Expecting equal subsets.
Took 0.000323 seconds
Checking: (1, 2, 3,  ... [snip: 994 elements] ..., 998, 999, 1000)
    Subsets: (1, 3, 5,  ... [snip: 495 elements] ..., 995, 997, 999)
         and (2, 4, 6,  ... [snip: 493 elements] ..., 996, 998, 1000)
    Subset sum = 250250
ok 33 - Expecting equal subsets.
Took 0.001866 seconds
Checking: (1, 1, 2, 2, 3, 3, 4, 4)
    Subsets: (1, 1, 2, 3, 3)
         and (2, 4, 4)
    Subset sum = 10
ok 34 - Expecting equal subsets.
Took 0.000212 seconds
Checking: (1, 1, 2,  ... [snip: 58 elements] ..., 31, 32, 32)
    Subsets: (1, 1, 3,  ... [snip: 27 elements] ..., 29, 31, 31)
         and (2, 2, 4,  ... [snip: 25 elements] ..., 30, 32, 32)
    Subset sum = 528
ok 35 - Expecting equal subsets.
Took 0.000310 seconds
Checking: (1, 1, 2,  ... [snip: 506 elements] ..., 255, 256, 256)
    Subsets: (1, 1, 3,  ... [snip: 251 elements] ..., 253, 255, 255)
         and (2, 2, 4,  ... [snip: 249 elements] ..., 254, 256, 256)
    Subset sum = 32896
ok 36 - Expecting equal subsets.
Took 0.001029 seconds
Checking: (1, 1, 2,  ... [snip: 4090 elements] ..., 2047, 2048, 2048)
    Subsets: (1, 1, 3,  ... [snip: 2043 elements] ..., 2045, 2047, 204
+7)
         and (2, 2, 4,  ... [snip: 2041 elements] ..., 2046, 2048, 204
+8)
    Subset sum = 2098176
ok 37 - Expecting equal subsets.
Took 0.006883 seconds
Checking: (1, 1, 2,  ... [snip: 32762 elements] ..., 16383, 16384, 163
+84)
    Subsets: (1, 1, 3,  ... [snip: 16379 elements] ..., 16381, 16383, 
+16383)
         and (2, 2, 4,  ... [snip: 16377 elements] ..., 16382, 16384, 
+16384)
    Subset sum = 134225920
ok 38 - Expecting equal subsets.
Took 0.054265 seconds
Checking: (1, 1, 2,  ... [snip: 262138 elements] ..., 131071, 131072, 
+131072)
    Subsets: (1, 1, 3,  ... [snip: 131067 elements] ..., 131069, 13107
+1, 131071)
         and (2, 2, 4,  ... [snip: 131065 elements] ..., 131070, 13107
+2, 131072)
    Subset sum = 8590000128
ok 39 - Expecting equal subsets.
Took 0.449057 seconds
Checking: (1, 1, 2,  ... [snip: 2097146 elements] ..., 1048575, 104857
+6, 1048576)
    Subsets: (1, 1, 3,  ... [snip: 1048571 elements] ..., 1048573, 104
+8575, 1048575)
         and (2, 2, 4,  ... [snip: 1048569 elements] ..., 1048574, 104
+8576, 1048576)
    Subset sum = 549756338176
ok 40 - Expecting equal subsets.
Took 3.644046 seconds
Checking: (1, 1, 2,  ... [snip: 16777210 elements] ..., 8388607, 83886
+08, 8388608)
    Subsets: (1, 1, 3,  ... [snip: 8388603 elements] ..., 8388605, 838
+8607, 8388607)
         and (2, 2, 4,  ... [snip: 8388601 elements] ..., 8388606, 838
+8608, 8388608)
    Subset sum = 35184376283136
ok 41 - Expecting equal subsets.
Took 89.489836 seconds
[download]

-- Ken

Comment on Re: Divide an array into 2 subsets to verify their sum is equal or not. Select or Download Code

Replies are listed 'Best First'.
Re^2: Divide an array into 2 subsets to verify their sum is equal or not. by hdb (Monsignor) on May 02, 2013 at 11:08 UTC
It does not work for `[ 8, 4, 4, 7, 6, 3 ]`. This is an NP-complete problem http://en.wikipedia.org/wiki/Knapsack_problem. Which means there is no (known) solution in polynomial time. Applies to BrowserUK's solution as well.	[reply] [d/l]
Re^3: Divide an array into 2 subsets to verify their sum is equal or not. by BrowserUk (Patriarch) on May 02, 2013 at 11:29 UTC
This is an NP-complete problem Only true if the OP was looking for an optimum solution. He isn't: Subset size is not matter, Behooves you to read the actual question. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' 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]
Re^3: Divide an array into 2 subsets to verify their sum is equal or not. by BrowserUk (Patriarch) on May 02, 2013 at 11:23 UTC
Applies to BrowserUK's solution as well. Look again :) #! perl -slw use strict; use Time::HiRes qw[ time ]; use List::Util qw[ sum ]; sub partition { my $sum = sum @_; return if $sum & 1; $sum /= 2; my @s = sort{ $b <=> $a } @_; my @a; my( $t, $n ) = ( 0, -1 ); $t + $s[$n] <= $sum and $t+= $s[$n] and push @a, $n while ++$n < @ +s and $t <= $sum; @a = delete @s[ @a ]; @s = grep defined, @s; return unless sum( @a ) == sum( @s ); return \@a, \@s; } my $start = time; my( $a, $b ) = partition 8, 4, 4, 7, 6, 3; my @set = map int( rand 100 ), 1 .. $N; printf "Took %f seconds\n", time() - $start; if( $a ) { printf "(%u) == sum( @{ $a } ) == sum( @{ $b } )\n", sum @$a; } else { print "No solution existed for 8, 4, 4, 7, 6, 3"; } __END__ No solution existed for 8, 4, 4, 7, 6, 3 Took 0.000258 seconds [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' 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. div	[reply] [d/l]
Re^4: Divide an array into 2 subsets to verify their sum is equal or not. by hdb (Monsignor) on May 02, 2013 at 11:27 UTC
8 + 4 + 4 = 16 = 7 + 6 + 3	[reply]
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. by BrowserUk (Patriarch) on May 02, 2013 at 11:32 UTC
Re^3: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem) by LanX (Saint) on May 02, 2013 at 22:08 UTC
> This is an NP-complete problem http://en.wikipedia.org/wiki/Knapsack_problem Yes, to be precise a sub class known as "Partition Problem". See WP article for some efficient algorithms and further links. I wonder who and why is posting well known scientific problems w/o references ...? Cheers Rolf ( addicted to the Perl Programming Language)	[reply]
Re^4: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem) by hdb (Monsignor) on May 03, 2013 at 08:14 UTC
And if kcott or BrowserUK manage to fix their programs, there is a $1,000,000 price on it: http://www.claymath.org/millennium/.	[reply]
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable)) by BrowserUk (Patriarch) on May 03, 2013 at 10:35 UTC
Re^6: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable)) by hdb (Monsignor) on May 03, 2013 at 11:17 UTC
Some notes below your chosen depth have not been shown here
Re^6: Divide an array into 2 subsets to verify their sum is equal or not. (NP != unsolvable)) by LanX (Saint) on May 03, 2013 at 19:31 UTC
Some notes below your chosen depth have not been shown here
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem) by kcott (Archbishop) on May 03, 2013 at 18:54 UTC
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem) by LanX (Saint) on May 03, 2013 at 11:47 UTC
Re^4: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem) by hdb (Monsignor) on May 03, 2013 at 05:52 UTC
There are some very talented people in this community, so perhaps if we post the one or other unsolved problem, some monk might find a solution...	[reply]
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem) by LanX (Saint) on May 03, 2013 at 11:41 UTC
Re^6: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem) by hdb (Monsignor) on May 03, 2013 at 12:11 UTC
Some notes below your chosen depth have not been shown here
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem) by bimleshsharma (Beadle) on May 03, 2013 at 06:48 UTC
Re^3: Divide an array into 2 subsets to verify their sum is equal or not. by kcott (Archbishop) on May 02, 2013 at 21:12 UTC
++ Thanks. I've rewritten the solution to handle those sorts of cases. -- Ken	[reply]
Re^4: Divide an array into 2 subsets to verify their sum is equal or not. by LanX (Saint) on May 02, 2013 at 22:29 UTC
Sorry, but your algorithm must still be wrong if this test passes `my @test_unequal_subsets = ( ... [8, 4, 4, 7, 6, 3], ... );` [download] 8+4+4=16 Cheers Rolf ( addicted to the Perl Programming Language)	[reply] [d/l]
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. by kcott (Archbishop) on May 02, 2013 at 22:47 UTC
Re^2: Divide an array into 2 subsets to verify their sum is equal or not. by roboticus (Chancellor) on May 02, 2013 at 11:00 UTC
kcott: `[ 7, 5, 3, 3]` ;^) ...roboticus When your only tool is a hammer, all problems look like your thumb.	[reply] [d/l]
Re^3: Divide an array into 2 subsets to verify their sum is equal or not. by kcott (Archbishop) on May 02, 2013 at 21:08 UTC
++ Thanks. That node was something of a minor disaster. I've rewritten the solution. -- Ken	[reply]
Re^2: Divide an array into 2 subsets to verify their sum is equal or not. by BrowserUk (Patriarch) on May 02, 2013 at 11:10 UTC
A couple of questions: Why pass in a reference if the first thing you are going to do is copy the reference array to a local array? `sub check_arrays { my @full_array = @{shift()};` [download] Why make a local copy of the array at all, when all the uses (join, sum, sort) of it require you to pass a list? Ie. Why not `my $sum = sum @$ref;` etc. Isn't re-summing your partial array over and over wildly inefficient? With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' 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] [d/l] [select]
Re^3: Divide an array into 2 subsets to verify their sum is equal or not. by kcott (Archbishop) on May 02, 2013 at 21:19 UTC
++ Thanks. All your points are perfectly valid. There were other issues as well. I've substantially rewritten the solution. -- Ken	[reply]