Said Limbic~Region:
I figured that it would be nearly impossible to tell the difference between a "truly" randomization of the list and one that resulted from many of my re-orderings. ... Unfortunately, he didn't know of one at that moment.

Something I meant to say on IRC, but didn't get to, was that I don't think your question here was exactly well-posed. Suppose someone asked you if you would be able to distinguish a true random number from one that was only pseudo-random. Of course, you can't; the question isn't really sensical. The question they need to be asking in that case is whether you would be able to tell a sequence of random numbers from a sequence of pseudo-random numbers. And in that case the answer is that yes, methods for doing that are well-studied.

So the question I think you need to ask here is whether a sequence of arrays shuffled by your method would be distinguishable from a sequence of arrays shuffled into truly random orders. And having thought about it a little more (but just a little) I think the answer is probably yes; you could apply analogs of many of the usual statistical tests for randomness to such arrays, and find out that actually the method you were using wasn't very random at all.

Section 3.3 of Knuth's The Art of Computer Programming goes into these tests in great detail.

Setion 3.4.2 discusses random shuffling methods, including the Fisher-Yates algorithm, and then says:

R. Salfi has pointed out that Algorithm P cannot possibly generate more than m distinct permutations when we obtain the uniform U's with a linear congruential sequence of modulus m, or indeed whenever we use a recurrence Un+1 = f(Un) for which Un can take only m different values, because the final permutation in such cases is entirely determined by the value of the first U that is generated. Thus for example, if m = 232, certain permutations of 13 elements will never occur, since 13! ≅ 1.42 × 232.

This was exactly my concern when I originally said that generating truly random permutations was impossible with the pseudorandom generators supplied with most programming languages, including Perl. The space of permutations is just too big. However, Knuth continues:

Section 3.5 shows that we need not despair about this.
I haven't read section 3.5 in a long time, and I don't have time to pore over it now to figure out what Knuth meant by that, unfortunately. So I really don't know what the situation is.

--
Mark Dominus
Perl Paraphernalia

In reply to Re: Random Math Question by Dominus
in thread Random Math Question 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.