There's no great way to do it that I can see. You can generate random numbers mod the bitset size until one happens to fall on the index of a 1. Of course if 1's are sparse, this can take a while.
You can count the number N of 1's and generate a random number I mod N. Then scan the bitset again for the (I + 1)th 1. To avoid scanning twice, you can accumulate a vector of indices where all the 1's lie and use the random number to choose an element from this vector. On Oct 14, 12:01 pm, sankalp srivastava <[email protected]> wrote: > How will one go about extracting a random number from a bitset ? > let's say i have a bitset > 100000010000101000100010001 > where 1 denote what numbers are currently present in the set > How can one extract these ones in a random manner .Generating a random > number modulo size of the bitset won't work as it can land upon a zero > value as well and this , in worst case can take O(size of bitset * > genarating pseudo random number ) time which is very costly . > Anybody knows how to do this ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
