Pathologically Eclectic Rubbish Lister PerlMonks

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

by davido (Cardinal)
 on May 03, 2013 at 16:10 UTC ( #1031920=note: print w/replies, xml ) Need Help??

Here's my try, using Algorithm::Bucketizer:

```use strict;
use warnings;
use Algorithm::Bucketizer;
use List::Util qw( sum );
use POSIX qw( ceil );

my @arrays = (
[ qw( 1 3 8 4 ) ],
[ qw( 1 6 2   ) ],
[ qw( 1 3 5 7 ) ],
);

foreach my \$array ( @arrays ) {
print "( @{\$array} ) can ",
can_evenly_distribute( @{\$array} ) ? '' : 'not ',
"be evenly distributed.\n";
}

sub can_evenly_distribute {
my @elements = @_;
my \$b_size = ceil( sum( @elements ) / 2 );

my \$b = Algorithm::Bucketizer->new(
bucketsize => \$b_size,
algorithm  => 'retry'
);

\$b->add_item( \$_, \$_ ) foreach @elements;

\$b->optimize( algorithm => 'random', maxrounds => @elements * 10 );

my @buckets = \$b->buckets;

return    @buckets == 2
&& sum( \$buckets[0]->items ) == sum( \$buckets[1]->items );

}

I haven't found any cases where it fails to return the correct answer... but having just said that, someone will probably find one. ;)

Dave

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

Create A New User
Node Status?
node history
Node Type: note [id://1031920]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (6)
As of 2018-11-21 11:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My code is most likely broken because:

Results (239 votes). Check out past polls.

Notices?