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

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

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

Replies are listed 'Best First'.
Re^4: Divide an array into 2 subsets to verify their sum is equal or not. by hdb (Monsignor) on May 02, 2013 at 11:27 UTC
8 + 4 + 4 = 16 = 7 + 6 + 3	[reply]
Re^5: Divide an array into 2 subsets to verify their sum is equal or not. by BrowserUk (Patriarch) on May 02, 2013 at 11:32 UTC
Good point! 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]


Welcome to the Monastery
	PerlMonks