
Fixed problem reported by ++LanX.

Added in the same timing metrics used by BrowserUk for comparison.

Added volume testing.

Added options: tmtest_more=01 switch Test::More tests off/on (def=1);
thtime_hires=01 switch Time::HiRes metrics off/on (def=1);
vtvolume_tests=01 switch volume tests off/on (def=0);
vpmvolume_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 '' => /(?>^_)([az])/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);
}
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
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