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

by hdb (Prior)
 on May 02, 2013 at 11:08 UTC ( #1031731=note: print w/ replies, xml ) Need Help??

It does not work for [ 8, 4, 4, 7, 6, 3 ]. This is an NP-complete problem http://en.wikipedia.org/wiki/Knapsack_problem. Which means there is no (known) solution in polynomial time. Applies to BrowserUK's solution as well.

Comment on Re^2: Divide an array into 2 subsets to verify their sum is equal or not.
Replies are listed 'Best First'.
Re^3: Divide an array into 2 subsets to verify their sum is equal or not.
by BrowserUk (Pope) on May 02, 2013 at 11:29 UTC
This is an NP-complete problem

Only true if the OP was looking for an optimum solution. He isn't:

Subset size is not matter,

Behooves you to read the actual question.

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.
Re^3: Divide an array into 2 subsets to verify their sum is equal or not.
by BrowserUk (Pope) on May 02, 2013 at 11:23 UTC
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.
div

8 + 4 + 4 = 16 = 7 + 6 + 3

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.
Re^3: Divide an array into 2 subsets to verify their sum is equal or not. (Partition Problem)
by LanX (Chancellor) on May 02, 2013 at 22:08 UTC
> This is an NP-complete problem http://en.wikipedia.org/wiki/Knapsack_problem

Yes, to be precise a sub class known as "Partition Problem".

See WP article for some efficient algorithms and further links.

I wonder who and why is posting well known scientific problems w/o references ...?

Cheers Rolf

( addicted to the Perl Programming Language)

And if kcott or BrowserUK manage to fix their programs, there is a \$1,000,000 price on it:

No. Those prizes -- and in particular, the P v NP prize -- are not up for grabs for finding solutions to particular, restricted or bounded examples of particular NP problems. The prize is for proving that there is a whole class of problems for which there are no solutions. Quite a different matter indeed.

Despite that the OPs problem is fairly loosely stated, it does contain the relaxation of sufficient constraints -- specifically, Subset size does not matter -- that it removes the need to find either 'all solutions' or 'the optimal solution'; and that means that the problem ceases to to be "NP-complete".

And that brings us to a theme I've seen repeated many times in many places over my career, and frequently revisited here at the monastery.The scenario goes like this: a requirement is identified as desirable. Upon analysis, the code required to implement that requirement is identified as being some variation upon one or more of the classical NP-Complete problems; and the CS majors and half-well-reads in the room will throw their collective hands up saying, "It can't be done"!

But, on the basis of ever fading memory and usually reliable gut feel, I'd estimate that 8 out of 10 occasions, there is scope within that "some variation upon", to allow a 'good enough' solution to be found and implemented. Often all that is required is to remove the constraint that a perfect solution must be found every time.

Take for example the bin-packing/sheet cutting problem. On the basis of strictly correct theory, businesses who's basic operating models equate to one or the other variations of this classical problem shouldn't be able to operate; and yet we have glass-cutting services and dress makers operating in every city and small town; and the entire modern world economy would be impossible without that cargo planes and container ships and freight trains and white van men went about their daily business.

Once you factor time into the equations and realise that it isn't necessary to find perfect or optimal solutions -- that a container with a little empty space; or few offcuts from each 7' x 10' sheet are acceptable within the operating margins of the business model -- then a whole raft of NP-complete "impossible" problems cease to be so.

Indeed, there is a whole field (actually several whole fields), of computer science dedicated to finding good enough solutions to intractable problems. Namely Genetic Algorithms and its many offshoots. But, as with all heuristical algorithms, you need to know where the constraints can be relaxed; or the costs not exceeded to apply them. Ie. For the OPs purpose, can an exact balance of sums be overridden by a time constraint?

As is so often the case when these problems come up, the original description is so devoid of detail, it is impossible to reach conclusions about constraints might be relaxed in order to achieve a 'good enough' solution. My tactic in these situations is to post a naive -- ie. known imperfect -- solution and then wait for the OP to come back and explain why it is not good enough.

It is inherent in the OPs specification that not all sets are solvable -- sets with odd totals have no integer bipartition; sets like 6,4,4,4,4,4 cannot be equally partitioned -- so the OPs purpose has to accommodate these possibilities. And if his procedures and processes can accommodate the impossible conditions; who's to say that they couldn't also accommodate a slightly imperfect solution, even when a perfect solution might be possible?

Only the OP. But, as is also often the case when these problems come up, s/he has chosen not to involve themselves further. Which is a shame, because reaching a near equal partition can be done very quickly by several of the posted attempts; and adding a time-constrained, GA giggle to that would probably be able to refine that to complete equality in 95%+ cases with a few minutes of CPU.

But who is going to be bothered to expend such development energies when the OP doesn't seem to be interested any longer.

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.
Only 1e6 dollars ?

L O L !

Cheers Rolf

( addicted to the Perl Programming Language)

I've fixed all reported bugs and updated my node.

Now, what's all this I hear about a million bucks? :-)

-- Ken

There are some very talented people in this community, so perhaps if we post the one or other unsolved problem, some monk might find a solution...

> There are some very talented people in this community

Unlikely, and during my studies of mathematics this was considered extremely unfair!

These are well investigated problems known to be very hard and w/o optimal solution but already good practical solutions.

They shouldn't be disguised as a hackers question.

Cheers Rolf

( addicted to the Perl Programming Language)

TRUE

Re^3: Divide an array into 2 subsets to verify their sum is equal or not.
by kcott (Canon) on May 02, 2013 at 21:12 UTC

++ Thanks. I've rewritten the solution to handle those sorts of cases.

-- Ken

Sorry, but your algorithm must still be wrong if this test passes
my @test_unequal_subsets = ( ... [8, 4, 4, 7, 6, 3], ... );

8+4+4=16

Cheers Rolf

( addicted to the Perl Programming Language)

Bugger! Yes, you're right. Thanks for pointing that out (++ when the Vote Fairy next visits). That should, of course, be in @test_equal_subsets (8+4+4 = 7+6+3 = 16). Back to the drawing board ...

Update: Bug fixed. Node updated.

-- Ken

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

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (13)
As of 2015-11-30 09:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?