in reply to Divide an array into 2 subsets to verify their sum is equal or not.

G'day bimleshsharma,

Update:

<Reveal this spoiler or all spoilers in this node or all in this thread>

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

<Reveal this spoiler>

Update3: Fixed a bug and added some features:

<Reveal this spoiler>

Update4: Fixed some bugs and changed volume testing.

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

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
[reply]
[d/l]
      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]
      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]

        8 + 4 + 4 = 16 = 7 + 6 + 3

[reply]
      > 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]
[reply]

        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]

      ++ Thanks. I've rewritten the solution to handle those sorts of cases.

      -- Ken

[reply]
        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^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]

      ++ 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:

    1. 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]
    2. 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.

    3. 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]

      ++ Thanks. All your points are perfectly valid. There were other issues as well. I've substantially rewritten the solution.

      -- Ken

[reply]

In Section Seekers of Perl Wisdom