Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

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

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


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

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.
  • Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (9)
As of 2018-07-16 20:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    It has been suggested to rename Perl 6 in order to boost its marketing potential. Which name would you prefer?















    Results (349 votes). Check out past polls.

    Notices?