Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: Algorithm to convert combinations to bitstring (size)

by tye (Sage)
on Oct 18, 2006 at 18:25 UTC ( [id://579162]=note: print w/replies, xml ) Need Help??


in reply to Algorithm to convert combinations to bitstring

I suspect it may be much faster to just assign one bit to each member of the superset and set that bit iff that member is in the subset. Then you need N bits not log2( C(N,K) ) bits. The size difference is likely to be fairly small (you don't mention your values for N and K, though I'm pretty sure you have specific values in mind) while the speed difference in conversion will likely be considerable.

Update: Alternately, if the size difference is huge, then that probably means that K is close to either 0 or N so you could use log2(N**K) or log2(N**(N-K)) bits and treat it as a base-N number where each "digit" represents a member of the subset.

Update2: In the ChatterBox, Limbic~Region explained that he wants to use the bit string to track a subset of the set of all possible combinations (one bit for each possible combination). So remove the log2()s from my equations and replace N with 2**N, which makes the space difference much more significant.

- tye        

Replies are listed 'Best First'.
Re^2: Algorithm to convert combinations to bitstring (size)
by Limbic~Region (Chancellor) on Oct 18, 2006 at 18:33 UTC
    tye,
    N = 26 always and I will have 25 different bitstrings for K = 1 .. 25. I am not sure I understand what you mean by your 1 bit per superset and then set the bit if that member is in the subset.
    ABCDE = 00000 AC = 10100 DE = 10100 + 00011 = 10111 ?

    Cheers - L~R

      26 bits isn't very many so A=2**0=1, B=2**1=2, ..., Z=2**25=0x2000000. ABZ=0x2000003.

      - tye        

        tye,
        Ok, I think what you are saying is count in base-N even though you don't need all the bits? If that's the case then yes, it may make things easier and the extra space shouldn't be that much more.

        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://579162]
help
Chatterbox?
and the web crawler heard nothing...

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

    No recent polls found