Randomly Sort an Array

[martin]

IMO Yashied's method is faulty although it might be fast. Instead of going through all elements and reallocating the values to a random location, a pair of random locations are chosen and then swapped. This means that there is a good chance that some locations will never be changed.

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[Yashied]

IMO Yashied's method is faulty although it might be fast. Instead of going through all elements and reallocating the values to a random location, a pair of random locations are chosen and then swapped. This means that there is a good chance that some locations will never be changed.

#775764

[martin]

#775764

But to overcome the limitation you are going over the operation many times. It doesn't make sense to me whereas the solution posted by jchd seems the most obvious and simplest and probably the fastest though I haven't tested any of them.

[jchd]

Oh don't believe it's _my_ solution. I goes back to before Knuth (Searching and Sorting) first edition, as the names of Fisher - Yates only appears in Knuth subsequent editions. I don't have my copies handy so I can't check right now. I also seem to recall a nice analysis by Knuth.

There is one drawback with these algorithms and this is contrary to what I wrote few posts ago: even if they offer good guarantee of randomness, it is possible to write an ad hoc test that will discriminate output of these algorithm from truly random runs, given sufficient samples. Here's why. Look at the classical implementation for a zero-based array A having N elements:

for i = N - 1 to 1 step -1

j ← random integer with 0 ≤ j ≤ i

exchange A[j] and A

It's plain that A[N-1] _will_ be swapped and it can only be swapped once. So we're sure that A[N-1] doesn't contain the initial value stored in A[N-1] input array. The fact that this is certain goes against true [pseudo-]randomness.

Elements A[N-2] down to A[0] will be [pseudo-]randomly swapped, so we can't assert anything about them.

So to restore true [pseudo-]randomness on the full range of elements, we would need to add after the end of the loop:

exchange A[N-1] and random element of index 0..N-2

It won't make any difference in most applications, but there can be cases were such weakness can be very important. E.g. if I know that the first card on the deck is the ace of spade before shuffle, then I also already know the first card in the shuffled deck will _not_ be the ace of spade. That would be unacceptable in a number of use!

EDIT: I thought completely wrong and wrote utter bullshit here. The algorithm is fine and doesn't need anything like that. Sorry.

Edited March 28, 2011 by jchd

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[jchd]

Implementation speed should only be a concern once provable correctness is asserted. Of course that's under a "once a suitable complexity algorithm is selected" assumption.

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[czardas]

Just to add to what's already been said: Pairing elements is pattern based. If the pairings are repeatedly selected at random, then there is a chance that some elements will return to their original positions. If the pairings are forced to swap only once, then there will be a very limited number of possible outcomes.

Edited May 3, 2010 by czardas

[jchd]

It's perfectly normal that some elements stay in place.

Shuffle a deck of cards in factory order. Shuffle it well and without cheating for half an hour.

Now, tell me that it would be abnormal that one or more cards would arrive at the same place than before shuffling. No, it's not. It would be very non-random biased if such possibility would be explicitely avoided. That translate into an observer knowing true assertions about a random event! That's not random anymore... Do that with a deck of two cards in standard order and you see that you know the resulting order even before shuffling occurs. In another context, it could make you avoid winning the goat everytime.

You could even return a well shuffled deck in factory order! Of course, the odds of such an event is very low, 1/(52!) for a 52-card deck, but it's not zero.

[czardas]

Yes I agree with you jchd. Forcing elements to change is not random at all, nor is that what I meant to imply. Perhaps I should have phrased it differently. I believe there is a higher probability of pairs remaining in position. Not single cards, but multiples of two. That seems to be a loaded deck of cards to me. I accept that the more you repeat the process, the less chance there will be of such pairings remaining intact.

Edited May 3, 2010 by czardas

[jchd]

Correct. The point was that there is no need to make multiple passes, as one pass does all (if, as I noted, you take the precaution to exchange of first element with a random one as explained earlier). This way, every element has an equal probability to arrive in any final position, which is what we intended.

1D array $A being [pseudo-]randomly shuffled to give array $B is the same as if we assign $B to be a [pseudo-]random row of _ArrayPermute($A)

but don't try _ArrayPermute() on a deck of 52 cards

[czardas]

but don't try _ArrayPermute() on a deck of 52 cards

Okay

[Tvern]

IMO Yashied's method is faulty although it might be fast. Instead of going through all elements and reallocating the values to a random location, a pair of random locations are chosen and then swapped. This means that there is a good chance that some locations will never be changed.

Thats why I wrote an _ArrayRandom UDF to swap each index with a random index, resulting in at at least 1 swap per item. Seems pretty fast as well.

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[Tvern]

Hmm nice. You limit the number of times the each value gets moved by re-using the spot that freed up by the last move.

That effectively reduces the number of moves by 33%. Looking at it that way I would actually have expected the performance gain to be bigger.

It looks like having Random return an integer is a little faster than your random method if you want to make it even faster. (very small difference)

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[Tvern]

I meant moves of values from one variable, or array index to another. My script does 3 of these for each value, while yours only does 2 for each value, plus 2 for the value stored in $vTmp. Meaning almost 1 in 3 moves are cut for larger arrays.

Ofcoarse this is a very fast action and the main slowdown appears to be in the calculation of Random(), which after a test with a larger pool turned out to be to-close-to-tell between the two different ways. (On my PC at least)

I'm going to do some more testing with the speed of Random, because I can't replicate your way being faster. (nor the opposite, which I thought I had tested to be true earlier)

Meh I'm convinced. I was changing the random part of your function, which blurred the results. Testing only the random function showed yours to be quite a lot faster. (about 20%).

I'll go away quietly now.

Edited March 27, 2011 by Tvern

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[MvGulik]

whatever Edited February 7, 2011 by MvGulik