[Home] [Downloads] [Search] [Help/forum]

Gammon Forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

[Folder]  Entire forum
-> [Folder]  MUSHclient
. -> [Folder]  Lua
. . -> [Subject]  Shuffle algorithm
Home  |  Users  |  Search  |  FAQ
Username:
Register forum user name
Password:
Forgotten password?

Shuffle algorithm

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page


Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Tue 08 Dec 2009 03:57 AM (UTC)

Amended on Fri 26 Aug 2011 12:07 AM (UTC) by Nick Gammon

Message
Another useful algorithm I found on Wikipedia is a shuffle algorithm for tables. This is handy for situations where you have a collection of data (eg. a pack of cards) and you want to present them randomly.


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


function shuffle(t)
  local n = #t
 
  while n >= 2 do
    -- n is now the last pertinent index
    local k = math.random(n) -- 1 <= k <= n
    -- Quick swap
    t[n], t[k] = t[k], t[n]
    n = n - 1
  end
 
  return t
end



An example of its use:


cards = { "Ace", "King", "Queen", "Jack", 10, 9, 8, 7, 6, 5, 4, 3, 2 }

shuffle (cards)

for k, v in ipairs (cards) do
  print (v)
end -- for

Output:

8
9
2
Queen
4
5
7
6
10
Jack
3
Ace
King


I used to use something similar to this in the days when MUSHclient had a delay dialog if you weren't registered. There was one button to press out of 10, and the order of the 10 buttons was shuffled using an algorithm like this.



[EDIT]

On 26 August 2011, changed:


  while n > 2 do


to:


  while n >= 2 do


- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by JPhilipp   (1 post)  [Biography] bio
Date Reply #1 on Thu 25 Aug 2011 09:15 PM (UTC)

Amended on Fri 26 Aug 2011 12:00 AM (UTC) by Nick Gammon

Message
Above shuffling doesn't fully work, you can most clearly see it when the table only has 2 items. Here is a fix:


function shuffleArray(array)
    local arrayCount = #array
    for i = arrayCount, 2, -1 do
        local j = math.random(1, i)
        array[i], array[j] = array[j], array[i]
    end
    return array
end


Thanks
[Go to top] top

Posted by Nick Gammon   Australia  (21,607 posts)  [Biography] bio   Forum Administrator
Date Reply #2 on Fri 26 Aug 2011 12:08 AM (UTC)
Message
Thanks for that! I think the edit I made in the original post has the same effect.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Derick Appiah   (5 posts)  [Biography] bio
Date Reply #3 on Sun 28 Jul 2013 07:23 PM (UTC)
Message
So please with regards to this subject, how can i unshuffle after having shuffled the table items or say values, using the same lua
[Go to top] top

Posted by Fiendish   USA  (1,744 posts)  [Biography] bio   Global Moderator
Date Reply #4 on Sun 28 Jul 2013 07:29 PM (UTC)

Amended on Sun 28 Jul 2013 07:31 PM (UTC) by Fiendish

Message
Quote:
So please with regards to this subject, how can i unshuffle after having shuffled the table items or say values, using the same lua


LIKE THIS!


require "copytable"
function shuffleArray(array)
    arrayBackup = copytable.deep(array)
    local arrayCount = #array
    for i = arrayCount, 2, -1 do
        local j = math.random(1, i)
        array[i], array[j] = array[j], array[i]
    end
    return array
end

function unshuffleArray(array)
    return arrayBackup
end


But seriously, you want to properly reverse a process that makes calls to math.random? Maybe you meant you want to sort? That's not the same as unshuffling.

https://github.com/fiendish/aardwolfclientpackage
[Go to top] top

Posted by Derick Appiah   (5 posts)  [Biography] bio
Date Reply #5 on Sun 28 Jul 2013 08:33 PM (UTC)
Message
But seriously, you want to properly reverse a process that makes calls to math.random? Maybe you meant you want to sort? That's not the same as unshuffling.


First of all let me commend you and the forum for been so consistent, especially following the quick responds. I strongly within my spirit honour this forum as one of the best i've witnessed
Well you may be right by the comment made, but, whiles googling, i came across several instances where some programmers in different programming languages have demonstrated how to reverse the shuffles made with the algorithm.
Even in some forums, they did use randomseed with key to shuffle and unshuffle.
Below are some of the forums or sites i'm refering to. However, my biggest challenge was as a newbie, i was finding it difficult to translate those languages used. I'm a strong fun of lua, as a beginner, is very easy and simple to learn
http://stackoverflow.com/questions/3541378/reversible-shuffle-algorithm-using-a-key

http://www.autohotkey.com/board/topic/91195-fisher-yates-shuffle-algorithm/

So how can something of this kind be done in lua, apart from the way you have just demonstrated? Thanks
[Go to top] top

Posted by Fiendish   USA  (1,744 posts)  [Biography] bio   Global Moderator
Date Reply #6 on Sun 28 Jul 2013 09:05 PM (UTC)

Amended on Sun 28 Jul 2013 09:06 PM (UTC) by Fiendish

Message
Ahh...of course!
If you choose a particular randomseed and store that value, then you can use it again and get back the same sequence of pseudo-random numbers that you got the first time. Then you just reverse the order of swaps.

How about this...


function shuffleArray(array)
    randseed = os.time()
    math.randomseed(randseed)
    local arrayCount = #array
    for i = arrayCount, 2, -1 do
        local j = math.random(1, i)
        array[i], array[j] = array[j], array[i]
    end
    return array
end

function unshuffleArray(array)
    math.randomseed(randseed)
    local arrayCount = #array
    swaps = {}
    for i = arrayCount, 2, -1 do
        table.insert(swaps, {i, math.random(1, i)})
    end
    for i = #swaps,1,-1 do
        array[swaps[i][1]], array[swaps[i][2]] = array[swaps[i][2]], array[swaps[i][1]]
    end
    return array
end


One problem with doing this is that repeated calls to math.randomseed can actually hurt the randomness.

https://github.com/fiendish/aardwolfclientpackage
[Go to top] top

Posted by Derick Appiah   (5 posts)  [Biography] bio
Date Reply #7 on Mon 29 Jul 2013 12:47 AM (UTC)
Message
Well man, i'm so so appreciative to your wonderful support. I'm very proud of you. I'm most greatful to have met such a generous, kind, enthusiastic, noble and patient personality like you in the forum. I shall forever remain greatful and loyal to your kindness. You are my master with whom i would like to share my problems! Thanks so much

Again, a very quick one, i having been trying since the last 2 months to find a way to toggle the mouse cursor from an arrow to hand, once it hover's over a hyperlink, but of all my googling, i can't find any lua function to help me do this in a RichText. Meanwhile, like i indicated in my earlier post, i have seen it being done in other languages, by passing a call to the User32 dll, but can't just find a way to implement it in lua. However, since you happen to be a genius, please, how best can you help me to implement this in lua, as a newbie.
Thank You!
[Go to top] top

Posted by Fiendish   USA  (1,744 posts)  [Biography] bio   Global Moderator
Date Reply #8 on Mon 29 Jul 2013 02:29 AM (UTC)

Amended on Mon 29 Jul 2013 02:31 AM (UTC) by Fiendish

Message
Ugh. This
Quote:
Well man, i'm so so appreciative to your wonderful support. I'm very proud of you. I'm most greatful to have met such a generous, kind, enthusiastic, noble and patient personality like you in the forum. I shall forever remain greatful and loyal to your kindness. You are my master with whom i would like to share my problems!

and this
Quote:
However, since you happen to be a genius, please, how best can you help me to implement this in lua, as a newbie.

are very annoying. Please stop. Just stick to asking questions.


But not in this thread. Make a new thread for unrelated questions.

https://github.com/fiendish/aardwolfclientpackage
[Go to top] top

Posted by Derick Appiah   (5 posts)  [Biography] bio
Date Reply #9 on Mon 29 Jul 2013 06:48 AM (UTC)
Message
Please i'm very sorry for my english. I didn't mean to hurt you, but to show appreciation for your responds. I learn english, so please forgive me. I will do as you have suggested. I'm very sorry! Please forgive me. I'm sorry!
[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


15,061 views.

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Go to topic:           Search the forum


[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at FutureQuest]