Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^4: Algorithm to convert combinations to bitstring

by Limbic~Region (Chancellor)
on Jan 01, 2010 at 19:49 UTC ( [id://815220]=note: print w/replies, xml ) Need Help??


in reply to Re^3: Algorithm to convert combinations to bitstring
in thread Algorithm to convert combinations to bitstring

spx2,
This doesn't meet the requirements. Since this thread is several years old, let me explain again what I was trying to accomplish.

You have a function that will perform an expensive operation the first time it is passed a unique argument list but is free to short circuit and return early if it has been called with the same arguments again. This is typically accomplished using a %seen hash or the Memoize module. Unfortunately, the number of possible argument variations is too large to use standard tools - hence the desire to use a bit string.

In my case, the arguments will always be a subset of a known set and they will always be a fixed size. On the other hand, we are not generating them - they will be passed to us. We need to convert the subset into an integer and either set that single bit if not already set and perform the expensive operation or return if already set.

In summary, if we are doing N Choose K with K = 13 and N = 26 then there are 10,400,600 total possible combinations. This means our seen should be exactly 1,300,075 bytes (1 bit representing each possible combination). If your solution requires more memory than that or is not able to take an arbitrary subset and convert it into an integer to see if the bit is set or not then it doesn't meet the requirements.

Cheers - L~R

Replies are listed 'Best First'.
Re^5: Algorithm to convert combinations to bitstring
by spx2 (Deacon) on Jan 10, 2010 at 14:57 UTC
    ok you're right :) how did you solve the problem ?
      spx2,
      See How many words does it take?. If I remember correctly, I modified blokhead's solution to Java. Since I was dealing with a powerset, I had 26 bitstrings - 1 for each possible length of string.

      Cheers - L~R

Log In?
Username:
Password:

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

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

    No recent polls found