TrueRandom or Not?

ID:156663
 
Aug 19 2010, 3:39 am (Edited on Aug 19 2010, 6:09 am)
 
proc/TrueRandom(list/TheDeck)
    var
        size = TheDeck.len
    while(size>0)
        TheDeck.Swap(rand(1,size),rand(1,TheDeck.len))
        size--

I've done alot of online reading lately about how to randomly shuffle a deck of 52 cards.
From what I read they all ultimately suggest to;
Switch A with B
Where A = A number between 1 and LoopCount
and B = Number btween 1 and DeckMax
LoopCount starts at the Deck's size and decreases.

This is proposed to be truly random as EACH position in the deck has an exactly equal chance of being swapped with another.

Lummox JR wrote:
This is a correct shuffling algorithm:

proc/Shuffle(list/deck)
>   if(!deck) return
>   for(var/i=deck.len, i>1, --i)
>     deck.Swap(i, rand(1,i))


Essentially what that's doing is building the shuffled deck from the bottom up, choosing a card at random from the unshuffled part (indexes 1 through i) and moving it to the shuffled pile (i+1 through deck.len), replacing it with another card. As the loop progresses, the growing shuffled pile is filled with cards in truly random order while the unshiffled pile becomes more random as it gets smaller.

The loop terminates when i==1 because at that point, the process of elimination has left you with only one card.
Aug 19 2010, 4:58 am
I haven't look around for any good algorithms, but I'm sure they're out there... google around a bit.

I'm not sure if this method has equal possibilities for each permutation, however here's a quick way to do it:

proc
    shuffle_array(var/list/a)
        . = a
        for(var/i=1;i<=a.len;i++)
            a[i] = pick(a)
Aug 19 2010, 5:14 am
In response to Haywire
Ironicaly, Googling around for a hour brought me to the same idea of code that I made in the 1st post. thank you for your revised version however.
Aug 19 2010, 5:26 am
That algorithm won't work, because you're not making sure every card has the potential to move to a new place. Every index should be used in a Swap() at some point unless it's swapping with itself. But your 2nd card could stay in its same position the whole time, because there is no guarantee that at any point either rand(1,size) or rand(1,TheDeck.len) will be 2.

To put it another way, a shuffle is basically a form of permutation. There are 52! possible outcomes for a shuffled deck of standard cards without jokers. The first card could be any of the 52, the second has to be one of the 51 remaining, and so on down to the last card. A proper permutation therefore has to always choose the nth card from whatever is left, but your algorithm doesn't do that; it can skip over indexes, never considering them for a swap at all.

This is a correct shuffling algorithm:

proc/Shuffle(list/deck)
  if(!deck) return
  for(var/i=deck.len, i>1, --i)
    deck.Swap(i, rand(1,i))


Essentially what that's doing is building the shuffled deck from the bottom up, choosing a card at random from the unshuffled part (indexes 1 through i) and moving it to the shuffled pile (i+1 through deck.len), replacing it with another card. As the loop progresses, the growing shuffled pile is filled with cards in truly random order while the unshiffled pile becomes more random as it gets smaller.

The loop terminates when i==1 because at that point, the process of elimination has left you with only one card.

Lummox JR
Aug 19 2010, 5:54 am
In response to Bunnie
Bunnie wrote:
Ironicaly, Googling around for a hour brought me to the same idea of code that I made in the 1st post. thank you for your revised version however.

Haywire's code is broken too, in more than one way. The main problem is that he's not doing a swap, so cards get duplicated. The other problem is that because he's always picking from the entire deck, shuffled or unshuffled, it's not a true permutation, therefore a poor shuffle. It will increase randomness more than your original code, but both are wrong.

Lummox JR
Aug 19 2010, 6:01 am
In response to Lummox JR
Would you mind offering some code so that we may learn from it?
Aug 19 2010, 6:03 am
In response to Bunnie
Bunnie wrote:
Would you mind offering some code so that we may learn from it?

Indeed not, which is why I already did.

Lummox JR
Aug 19 2010, 6:04 am
In response to Lummox JR
Lummox JR wrote:
Bunnie wrote:
Would you mind offering some code so that we may learn from it?

Indeed not, which is why I already did.

Lummox JR
Oh I apologize. I already looked at your corrected code and mis-stook your comment for saying that it wasn't the correct method. I apologize. Thanks again, I can see (quite plainly) where I could've improved.

As a question though. This formulae works for ANY pile of cards, right? so it could work for a UNO deck or a 52 Pile of Cards? etc?
Aug 19 2010, 6:07 am
In response to Bunnie
Bunnie wrote:
As a question though. This formulae works for ANY pile of cards, right? so it could work for a UNO deck or a 52 Pile of Cards? etc?

Like any algorithm it's just math and logic. A deck of cards is a deck of cards; size is irrelevant. It's just swapping abstract things in a list, which could be anything. It could be a song playlist or a list of names just as easily.

Lummox JR