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?? |
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 Section
Seekers of Perl Wisdom
|
|