Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

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

by choroba (Abbot)
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"; }
لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ


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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1031705]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (6)
As of 2014-12-28 17:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (182 votes), past polls