comment on

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

In reply to Re: Algorithm to convert combinations to bitstring (size) by tye
in thread Algorithm to convert combinations to bitstring by Limbic~Region

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.