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

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.