How should I scramble a table?

[Mr. Strange]

I have a table of 52 elements - a deck of cards. I want to shuffle them - that is, assign each of the 52 elements to a new, unique, random location.

My first idea was to use table.sort along with some random number generator. I could assign each element a random value, and then sort by those, or maybe I could do the whole thing in one step? Someone must have figured out a slick way to do this. My potentially clumsy attempt:

(assume the random number generator has been seeded previously.)

Code: Select all

table = {}
for i=1,100 do
     table[i] = i
end

mixer = {}
for i=1, #table do
     mixer[i] = math.random()
end

... now I want to do table.sort on mixer, and apply the same transposition of elements to table. Maybe I can't do that? Could I sort table by providing a comparison function which references values in mixer?

--Mr. Strange

[surtic]

I think the "standard" way to shuffle an array is this:

Code: Select all

function shuffle(tab)
  local len = #tab
  local r, tmp
  for i = 1, len do
    r = math.random(i, len)
    tmp = tab[i]
    tab[i] = tab[r]
    tab[r] = tmp
  end
end

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

edit: you can also read a bit more at http://en.wikipedia.org/wiki/Shuffle#Sh ... algorithms which describes your method as well (which is slightly less efficient because sorting an array is slower than just traversing it).

[Kaze]

Code: Select all

    tmp = tab[i]
    tab[i] = tab[r]
    tab[r] = tmp

Code: Select all

tab[i], tab[r] = tab[r], tab[i]

[Mr. Strange]

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

edit: you can also read a bit more at http://en.wikipedia.org/wiki/Shuffle#Sh ... algorithms which describes your method as well (which is slightly less efficient because sorting an array is slower than just traversing it).

Perfect. Thank you.

--Mr. Strange

[surtic]

Kaze, you're right... too many years of bad habits...

Sometimes I do catch myself and use the idom "a, b = b, a" but in many other cases the code just looks right to me...

[Codex]

So the earlier post was a way to shuffle a single array. (ex. a deck of cards)

-snip-

-snip-

Code: Select all

function shuffle(tab)
  local len = #tab
  local r
  for i = 1, len do
    r = math.random(i, len)
    tab[i], tab[r] = tab[r], tab[i]
  end
end

For a project I'm working on, I needed to shuffle tables inside one another. (ex. table[x][y]) So after playing with the above formula a bit, I came up with this.

Code: Select all

function shuffle(tab)
  local x_len = #tab
  local r_x, r_y
  for x=1, x_len do
    local y_len = #tab[x]
      for y=1, y_len do
        r_x = math.random(x, x_len)
        r_y = math.random(y, y_len)
        tab[x][y], tab[r_x][r_y] = tab[r_x][r_y], tab[x][y]
    end
  end
end

This lets me generate an image that is stored in an [x][y] format randomly.



I'm very pleased with the result!

(edit: Also I feel this thread belongs in the support and development more than general section...?)

[qaisjp]

Code: Select all

function shuffle(tab)
  local len = #tab
  local r
  for i = 1, len do
    r = math.random(i, len)

    tab[i], tab[r] = type(tab[r])=="table" and shuffle(tab[r]) or tab[r], type(tab[i])=="table" and shuffle(tab[i]) or tab[i]
  end
end

[Roland_Yonaba]

Err... Why always testing if tab[r] is a table ?

[qaisjp]

Err... Why always testing if tab[r] is a table ?

deep scrambling - if this was the table:

Code: Select all

{
   {1, 2, 3},
   {4, {5, 6}, 7, {8, 9, {10, 11} }}
}

I'd get something like this:

Code: Select all

{
     {7, {9, {11, 10}, 8}, {6, 5}, 4},
     {2, 1, 3}
}

[tv_user]

Code: Select all

tab[i], tab[r] = type(tab[r])=="table" and shuffle(tab[r]) or tab[r], type(tab[i])=="table" and shuffle(tab[i]) or tab[i]

I just love these mind-twisting assignment operations! Nice and simple solution qaisjp!