Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: Better algorithm than brute-force stack for combinatorial problems?

by kvale (Monsignor)
on May 21, 2004 at 21:12 UTC ( [id://355464]=note: print w/replies, xml ) Need Help??


in reply to Better algorithm than brute-force stack for combinatorial problems?

The problem you are solving is a variation of the Subset Sum problem, and is known to be NP complete. There exist algorithms that are a little better than brute force, but still exponential in the number of elements.

Here is my take on the problem:

my @check = qw/ 1 2 3 4 5 6 7 8 9 /; my $desired = 20; foreach my $index (0..2**@check-1) { my $sum = 0; foreach my $pos (0..@check-1) { my $bit = ($index >> $pos) % 2; $sum += $bit * $check[$pos]; } if ($sum == $desired) { my @combo; foreach my $pos (0..@check-1) { push @combo, $check[$pos] if ($index >> $pos) % 2; } print join " ", @combo, "\n"; } }
On a 32 bit machine, this works for up to 32 numbers.

-Mark

  • Comment on Re: Better algorithm than brute-force stack for combinatorial problems?
  • Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://355464]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (6)
As of 2024-05-18 16:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found