more useful options PerlMonks

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

by BrowserUk (Pope)
 on May 02, 2013 at 09:51 UTC ( #1031717=note: print w/replies, xml ) Need Help??

choroba's Explore-all-possible-combinations mechanism works okay for smallish sets (max:32 or 64 depending upon your Perl), but will get very slow for anything much larger than 20 or so.

This will very quickly (less than 0.001 of a second) find a solution, if one exists, for sets of 100s or 1000s of elements. :

```#! 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;
}

our \$N //= 64;

my( \$a, \$b ) = partition 1,3,5,7;
print "sum( @{ \$a } ) == sum( @{ \$b } )" if \$a;

my @set = map int( rand 100 ), 1 .. \$N;

my \$start = time;
( \$a, \$b ) = partition @set;
printf "Took %f seconds\n", time() - \$start;

if( \$a ) {
printf "(%u) == sum( @{ \$a } ) == sum( @{ \$b } )\n", sum @\$a;
}
else {
print "No solution existed for the \$N element set @set";
}

A few runs:

```C:\test>1031699 -N=1e1
sum( 7 1 ) == sum( 5 3 )
Took 0.000042 seconds
No solution existed for the 1e1 elemet set 19 41 38 74 95 79 28 90 86
+87

C:\test>1031699 -N=1e1
sum( 7 1 ) == sum( 5 3 )
Took 0.000093 seconds
(184) == sum( 99 53 28 2 2 ) == sum( 91 48 24 11 10 )

C:\test>1031699 -N=1e2
sum( 7 1 ) == sum( 5 3 )
Took 0.000186 seconds
(2418) == sum( 99 98 97 97 96 95 95 93 90 89 88 88 84 84 82 82 82 81 8
+0 79 75 74 73 73 73 72 71 69 59 ) == sum( 67 67 66 65 64 62 61 60 58
+57 57 55 55 51 51 51 49 49 47 47 45 44 42 42 41 41 40 38 38 37 36 35
+34 34 34 33 33 32 31 31 29 28 28 27 27 27 26 26 24 24 23 23 21 20 20
+16 16 15 14 13 13 12 12 11 10 8 7 6 5 5 2 )

C:\test>1031699 -N=1e3
sum( 7 1 ) == sum( 5 3 )
Took 0.001379 seconds
(25172) == sum( 99 99 99 99 ...  71 71 71 70 70 70 33 0 0 0 ) == sum(
+70 70 70 70 70 70  ... 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 )

C:\test>1031699 -N=1e3
sum( 7 1 ) == sum( 5 3 )
Took 0.000053 seconds
No solution existed for the 1e3 elemet set 26 ... 93 10 10

C:\test>1031699 -N=1e4
sum( 7 1 ) == sum( 5 3 )
Took 0.013463 seconds
(247975) == sum( 99 99 ... 0 0 0 0 0 0 0 0 0 ) == sum( 70 70 ... 1 1 1
+ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 )

C:\test>1031699 -N=1e4
sum( 7 1 ) == sum( 5 3 )
Took 0.000238 seconds
No solution existed for the 1e4 elemet set 60 ...72 43 21 61 24 16

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^2: Divide an array into 2 subsets to verify their sum is equal or not.
by choroba (Bishop) on May 02, 2013 at 10:52 UTC
It gives a wrong answer for
```2, 12, 4
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Corrected. Thanks.

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.

Create A New User
Node Status?
node history
Node Type: note [id://1031717]
help
Chatterbox?
 [Discipulus]: yes sorry forget and forgive me [Eily]: for what it's worth I didn't go for the brightest solution either [Eily]: I tried print eval '2+1/3*(2+2/5))' or print \$@ [Eily]: and therefore concluded that the eval did succeed because there was no printed error :P [Eily]: stupid operator precedence :D

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (9)
As of 2017-10-24 10:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My fridge is mostly full of:

Results (287 votes). Check out past polls.

Notices?