Random / Table Shuffle

Solar2D Lua Language
#1

Hello,

I was able to make a simple shuffle function for tables. It works fine but I noticed the last item in the shuffled table is always the same. How can I fix this? Any ideas?

[code]
math.randomseed (os.time())
function shuffle(a)
local n = #a
local t
local k
while(n > 0) do
t = a[n]
k = math.random(n)
a[n] = a[k]
a[k] = t
n = n - 1
end
return a
end

– TEST
local list = {“a”, “b”, “c”, “d”, “e”, “f”, “g”, “h”, “i”, “j”};
local shuffledList = shuffle(list)
print(table.concat(shuffledList, “,”))
[/code] [import]uid: 3544 topic_id: 313 reply_id: 300313[/import]

#2

Running the code and looking over the output, it seems the odd shuffling results come from the poor random number generator* (1st “random” number generated is always ‘1’) and also because each time through the loop your lowering the size of the random number pool (1st loop, pool of 10 numbers; 2nd loop, pool of 9 numbers; and so on).

A shuffling method which I’ve used is simply to loop through the list of numbers a few times, picking two indexes at random and swapping their values.

Here’s some code:

--- code start ---  
local function shuffle( a )  
 local c = #a  
 math.randomseed( system.getTimer() )  
 for i = 1, (c \* 20) do  
 local ndx0 = math.random( 1, c )  
 local ndx1 = math.random( 1, c )  
 local temp = a[ndx0]  
 a[ndx0] = a[ndx1]  
 a[ndx1] = temp  
 end  
 return a  
end  
--- code end ---

It’s simple, short and quick. The sample loops through the table 20 times (which takes about a split second), but a smaller number can be used and still get good results.

HTH

*From the docs: “This function is an interface to the simple pseudo-random generator function rand provided
by ANSI C. (No guarantees can be given for its statistical properties.)” Nuff said. [import]uid: 1581 topic_id: 313 reply_id: 463[/import]

#3

Sweet! Thanks DGuy! My code was a port from Actionscript but didnt quite make good results.

Cheers! [import]uid: 3544 topic_id: 313 reply_id: 464[/import]

#4

I just needed something similiar and used the code above but modified it like this:

function shuffle( a )  
 local c = #a  
 for i = 1, c do  
 local ndx0 = math.random( 1, c )  
 a[ndx0], a[i] = a[i], a[ndx0]  
 end  
 return a  
end

First of… I seed the random number generator just in the beginning of the application (just posted some code for that in the code examples section)

Second… I believe you get enough randomness for most applications using just one run through all indexes and swap them once.

Third… If I can’t use ++ or += in Lua I need to use the x,y=y,x assignments… :wink:

At least my tests looked pretty nice and the above code is much faster and with less “magic” than the original.

Feel free to comment! [import]uid: 6928 topic_id: 313 reply_id: 3005[/import]

#5

There is a know “issue” that the first call to math.random always returns the same value. You should do an extra call to math.random after you call math.randomseed and throw away the results.

Tom [import]uid: 6119 topic_id: 313 reply_id: 3044[/import]

#6

Not sure to whom you reply … This is what I do in the seeding code snippet I posted in the example code section. But thank you for the heads up … people may miss that (and if it still is like this… it should get fixed in the sdk) [import]uid: 6928 topic_id: 313 reply_id: 3050[/import]

#7

@OderWat,

Your code looks correct for calling math.random() before using it. The problem was present in the SDK a number of builds ago and I haven’t seen it on the “fixed” list. In fact I’m not sure if it classified as a bug.

I did verify that the problem still exists in Beta 5. The first math.random() call after a math.randomseed() call will return the same number everytime. The returned number is not always 1 and depends on the arguments given.

Tom [import]uid: 6119 topic_id: 313 reply_id: 3054[/import]