G'day bimleshsharma,
Update:
Update2:
Original solution substantially rewritten! It had various problems:
Update3:
Fixed a bug and added some features:
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);
}
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
| [reply] [d/l] [select] |