All,
I popped into #perl today to catch the tail end of a question with Dominus and another chatter regarding randomizing a list of 100_000 elements. Dominus stated he would be surprised if any language had any built-in random number generator suitable for randomizing 100K elements because of the amount of entropy needed.

Well I wanted to be argumentative as it had been weeks since I used IRC. Once the other chatter was satisfied with pseudo-randomness, I said that repeating the randomization on larger and smaller scales should result in an overall random list. I was thinking a reverse bin sort and here is the process I outlined. (Assume we have 64 elements in our list but only enough entropy to truly randomize 8). 

A = 01-08, B = 09-16, C = 17-24, D = 25-32
E = 33-40, F = 41-48, G = 49-56, H = 57-64

Shuffle A - H

In turn, shuffle all 8 elements of each group as though it were a sing
+le list.

Wash, rinse, repeat

[download]

At this point, I was no longer interested in arguing for the sake of arguing (too bad my high school didn't have a debate team). I conceded the point of "truly" random but asked Dominus if he had any way of proving his assertion. 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. In other words, I was happy to trade linear time and only processing the list once for missing bits of randomness. Unfortunately, he didn't know of one at that moment. So I have two questions.

This entry on shuffling describes a process when using cards but I would like to see it applied to a list.

Cheers - L~R

* - For some definition of acceptable

In reply to 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.