Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: amount permutations

by kvale (Monsignor)
on Mar 04, 2004 at 18:34 UTC ( [id://333959]=note: print w/replies, xml ) Need Help??


in reply to amount permutations

Here is a simpler program that accomplishes the same thing for up to 32 checks:
my @check = (10, 5, 13, 3, 15, 1); my $desired = 16; 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"; } }
Here I index the possibilities with a simple integer expressing a binary combination of checks.

Timing was 55 milliseconds on an Athlon 2100.

-Mark

Replies are listed 'Best First'.
Re: Re: amount permutations
by gr0k (Novice) on Mar 04, 2004 at 19:12 UTC
    It will take me a while to try and figure out what you're code is doing, but do you mean this method will only work with up to 32 checks? My recordset could have hundreds of records in it. My example just had 6.
      The limitation is just the typical number of bits in an integer on 32-bit machines.

      Let me reiterate Abigails sound advice, however. Say you have 100 checks. Then any exhaustive search will take 2**100 tries. That is around 10**30, so for 1 msec per try, the program would take 10**27 seconds. The age of the universe is only around 5 * 10**17 sec, so exhaustive search is hopeless.

      Even creating a more clever branch-and-bound algorithm will only potentially reduce the factor of 2 a little.

      So I think you need to rethink your task. Do you really need exact amounts, or can you approximate? If all the checks were even, but the desired amout was odd, there would be no solution; would your business collapse at that point? Look at what you can do to relax the constraints. There are fine polynomial heuristics for the knapsack problem that get you close in a modest time.

      -Mark

        I knew going into this that we could only check so many combinations. Thats why I was searching only down to a configurable depth, probably only 3 to 5 deep. (A, AB, ABC, ABCD, etc) And unfortunately we need exact amounts. :( So we could have checks such as $100.30 and $20.75 to match for a search for $121.05.

        I'm no mathematician, but I've certainly learned a lot from researching the knapsack problem. If anything it's given me some backing in telling the boss that there's only so much I can do to speed this up. :)

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (9)
As of 2024-03-28 09:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found