bart,
I mean, picking an item, and if it's already been picked, try again

That is not what this code does. It automatically defaults to finding the nearest unselected bit. It does this using a regex to find the first byte that is not all ones and then examining that byte bit by bit.

Anyway, though you do take care to make sure every loop finds at least one item, you will not get a nice even distribution.

While I didn't say statistically uniform distribution was a necessity, it is a nicetey.

Suppose that your $N is 20, and by some weird coincidence, the numbers 1 .. 10 have already been picked, and nothing else. For your next pick, the numbers 12 to 20 all have 1 chance in 21 of being picked.

This is just not true. The random number is not selected over the entire range but only between 2 floating end points. Those end points move everytime they are selected.

Net result: there's 12 chances in 21, that is over 50%, that the next number picked, will be either 0 or 11.

This is also not true. Given the way the code works in your example, all unchosen bits have the same probability of being chosen.

As I have indicated in other replies, uneven statistical distribution is still possible even though:

This is because as holes get larger, the probability one of the two numbers on either side will be chosen increases. Theoretically those holes should all grow at the same rate, but I haven't taken the time to analyze it.

Cheers - L~R

In reply to Re^4: Generating 0 .. N Randomly and Efficiently by Limbic~Region
in thread Generating 0 .. N Randomly and Efficiently 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.