Please explain (Shuffling Cards Algorithm)

Solar2D General Questions/Discussion
#1

local function shuffleTable( t )

    local rand = math.random 

    assert( t, “shuffleTable() expected a table, got nil” )

    local iterations = #t

    local j

    

    for i = iterations, 2, -1 do

        j = rand(i)

        t[i], t[j] = t[j], t[i]

    end

end

I have found this code when searching for an algorithm for card shuffling, after several attempts to create one on my own. It works perfectly, but I need someone to explain it to me, the mentality behind this piece of code.

Thanks in advance.

#2

yeah i had the same problem then Rob Miracle explained it here.

http://forums.coronalabs.com/topic/46555-i-want-to-pick-20-random-numbers-without-repeating-any/

T.

#3

thanks ToeKnee,

and thanks Rob 

:slight_smile:

#4

google “fisher-yates shuffle” (or “knuth shuffle”) if curious for a technical treatment of how it works

#5

It took me a little while to figure out exactly what that code was doing (and I’ve been doing this for a very long time).   It kinda works like this:

Lets look at an example.  Take a deck of cards and pull one card at random from the deck and set it aside.  Next pull the next card at random and stack it on top of the card you previously pulled. Do this until your down to the last card and put it on the pile.   But in this example we really created two decks, the one you are taking cards from and the one you’re adding cards too.  

For efficiency (not creating a temporary table to hold the shuffled deck), this behaves more like:  Pull a card randomly from the deck of cards that have yet to be pulled and place it on top of the deck.   Pull the next card at random from the cards that have not been pulled from, place it on top of the deck of previously pulled cards.  Eventually you run out of cards that haven’t been pulled and the deck has been fully shuffled.

Rob

#6

yeah i had the same problem then Rob Miracle explained it here.

http://forums.coronalabs.com/topic/46555-i-want-to-pick-20-random-numbers-without-repeating-any/

T.

#7

thanks ToeKnee,

and thanks Rob 

:slight_smile:

#8

google “fisher-yates shuffle” (or “knuth shuffle”) if curious for a technical treatment of how it works

#9

It took me a little while to figure out exactly what that code was doing (and I’ve been doing this for a very long time).   It kinda works like this:

Lets look at an example.  Take a deck of cards and pull one card at random from the deck and set it aside.  Next pull the next card at random and stack it on top of the card you previously pulled. Do this until your down to the last card and put it on the pile.   But in this example we really created two decks, the one you are taking cards from and the one you’re adding cards too.  

For efficiency (not creating a temporary table to hold the shuffled deck), this behaves more like:  Pull a card randomly from the deck of cards that have yet to be pulled and place it on top of the deck.   Pull the next card at random from the cards that have not been pulled from, place it on top of the deck of previously pulled cards.  Eventually you run out of cards that haven’t been pulled and the deck has been fully shuffled.

Rob