Re: Randomly outputting an array

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".

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.

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: A second beginners question
    ... I am working on shuffling my array. ... > basics of shuffling the array, ... > close CONTROL2; ... then in the very next line destroy @newgroup by closing the block. ...
    (perl.beginners)
  • Re: Randomly outputting an array
    ... That was a stupid question, ... there are lots of ways of shuffling an array that ... for shuffling an array and I realized why it's structured exactly the ... Algorithm P given by Professor Knuth in Seminumerical Algorithms, ...
    (comp.programming)
  • 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: Shuffling without Swapping
    ... deck after the second game in order to continue playing. ... I am shuffling s-boxes many times during encryption. ... would want to shuffle one array using another already shuffled array. ... >> It would be possible to generate a standard pseudorandom sequence drawn ...
    (sci.crypt)
  • Re: random permutation of an array
    ... The following is a generalized shuffling routine that I have posted in the past over in the compiled VB newsgroups, but it works fine in the VBA world of Excel as well. ... Give it an array of elements and it will put them in random order and return the randomized elements back in the original array that was passed to it. ... Static RanBefore As Boolean ...
    (microsoft.public.excel.programming)