blokhead,
Ok, color me confused. First you say:

If my random number generator happened to pick 0,4,1,2,3 as the initial segment of the permutation, then with probability 1/2 the next number in the permutation will be either 5 or 9, while the other 1/2 of the probability is shared among 6, 7, and 8. They are not all equally likely! In a truly random permutation, all yet-unselected numbers will be equally likely as being the next one to appear. Emphasis mine.

Then I point out that, no, in my code and that situation all unchosen numbers would indeed have the same probability of being chosen. And then you say:

Yes, that's my point ;)

Um - which is it?

With regards to probability distribution: My solution is not auto-correcting. It starts out assuming uniform probability distribution but does not correct for it if it randomly goes awry. The "holes" should grow uniformly at the same rate since initial selection is random, direction to look is random, and end points move to keep the pool balanced on the ends. The trouble is that not all holes do form evenly. I can't prove that this is no different than a random permutation but I haven't seen any proof that it isn't either.

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.