in reply to Re^2: Divide an array into 2 subsets to verify their sum is equal or not.
in thread 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
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.
|
---|
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 | |
by BrowserUk (Patriarch) on May 02, 2013 at 11:32 UTC |
In Section
Seekers of Perl Wisdom