Re: Randomly outputting an array

Logan Shaw wrote:
Ico wrote:
Ico <usenet@xxxxxxx> wrote:

Is N times swapping two elements considered enough to truly 'randomize'
an array ?

That was a stupid question, please ignore me...

Actually, it's not a stupid question. It's a very good question.
The answer is definitely "no".

Thankyou, I'm glad somebody pointed this out.


It turns out, there are lots of ways of shuffling an array that
will not[1] really shuffle it properly. The key is getting every
element to have an equal chance of popping up in any other location.
That may be a little harder than it looks, or at least a little
easier to screw up than it looks.

Unfortunately, I only have a second to write this post, but I remember
taking a probability course in college and, while I was taking it,
looking into this exact issue. I looked at the Fisher-Yates algorithm
for shuffling an array and I realized why it's structured exactly the
way it is and why it has to be that way.

That is probably the simplest correct method, apparently the same as
Algorithm P given by Professor Knuth in Seminumerical Algorithms, 3.4.2
Random Sampling and Shuffling. I think a couple of other posters here
have suggested it. A lot of people call this the "Knuth shuffle", but
he credits L.E. Moses and R.V. Oakford (1963).

See: http://en.wikipedia.org/wiki/Knuth_shuffle


I wish I had more time to delve into this right now, and that my
knowledge of probability were still fresh, but I believe it is
important, if you care about having a truly random arrangement of
array elements afterwards (rather than having slightly higher odds
of elements at the beginning ending up at the end or something)
to use the right algorithm.

- Logan

[1] even assuming a random number generator that generates truly
random numbers.

.

Relevant Pages

  • Re: Q: Algorithm M vs. P of Knuths book
    ... > a PRNG) in some sense more random by shuffling it through ... > other hand, if one has an array filled with the numbers, ... > of the array elements with algorithm P and then output ... We might consider the entropy of an element's output position ...
    (sci.crypt)
  • Re: Q: Algorithm M vs. P of Knuths book
    ... >>more random by shuffling it through an array according to Algorithm M of Knuth ... > PRNG, then outputs them in a scrambled order. ...
    (comp.programming)
  • Re: Some tips and tricks
    ... The section 'shuffle the Array' looks rather dodgy. ... What will happen depends on the underlying sorting algorithm, ... last element has a 50% chance of staying where it is, ... It's not even remotely usable for actual shuffling. ...
    (comp.lang.javascript)
  • Q: Algorithm M vs. P of Knuths book
    ... One could render a sequence of numbers (typically from ... a PRNG) in some sense more random by shuffling it through ... an array according to Algorithm M of Knuth vol.2. ...
    (sci.crypt)
  • Q: Algorithm M vs. P of Knuths book
    ... One could render a sequence of numbers (typically from ... a PRNG) in some sense more random by shuffling it through ... an array according to Algorithm M of Knuth vol.2. ...
    (comp.programming)