Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

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

by choroba (Bishop)
on May 02, 2013 at 07:50 UTC ( #1031705=note: print w/replies, xml ) Need Help??

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

To sum a list, I used the sum from List::Util. I made the following observation: if the array can be split, then the sum of each part is the half of the sum of the whole array. I used vec to generate binary vectors to be used as Indicator function. Checking a half of the possible vectors is enough, the rest is complementary (i.e. the two subsets are swapped).
#!/usr/bin/perl use warnings; use strict; use List::Util qw(sum); sub is_divisible { my $array = shift; my $sum = sum(@$array) / 2; for my $bitmask (1 .. 2 ** $#$array - 1) { return 1 if sum(map { $array->[$_] * vec $bitmask, $_, 1} 0 .. + $#$array) == $sum; } return; } my @arrays = ( [qw(1 3 5 7)], [qw(1 3 8 4)], [qw(1 6 2)], [qw(5 5 4 6 2 8 1 9)], ); for my $array (@arrays) { print "@$array: ", is_divisible($array) ? 'yes' : 'no', "\n"; }
لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1031705]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (6)
As of 2017-10-22 23:06 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (275 votes). Check out past polls.