Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:
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
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.
- How many iterations of my process would it take before you had an acceptable* fake?
- Using code, how can you determine the amount of randomness of a given list?
Cheers - L~R