[Code Optimization] Generate random list of numbers with no repeats

[captain_cowell]

Topic says it all. I’ve set out to create a random number generator for an ARRAY of numbers with no repeats. Not terribly advanced or anything like that, but I just wanted to make sure I have the best possible run-time. I realize something like this isn’t going to break the bank with app performance, it’s more of a curiosity for me because run-time analysis isn’t exactly my strong suit.

I *think* the run-time for this is O(n). Would that be safe to say? Can you guys think of any algorithms that would be more efficient? I tried googling this but didn’t come up with much. Thanks!
[lua]–Generates a random set of NUM numbers between LOW and HIGH with no repeats
–Returns array RANDOMS which contains the random set of numbers with no repeats
function randomsNonRepeat(low,high, num)
local numList = {}
local randoms={}
local temp

for i=low, high do
numList[#numList + 1] = i
end

for j=1, num do
temp=math.random(low, #numList)
randoms[#randoms+1] = numList[temp]
table.remove(numList, temp)
end

return randoms

end[/lua]

Thanks!
[import]uid: 52208 topic_id: 18726 reply_id: 318726[/import]

[me7]

I will do some minor nitpicking first, then progress towards the big picture:

1. You might want to add an assert(num <= high - low + 1) to the header, and perhaps an assert(low <= high).

2. I would just use table.insert instead of numlist[#numlist + 1] and randoms[#random+1] for clarity and consistence with the table.remove you use.

3. Very probable bug: Beware numList is indexed from 1 to (high - low + 1), which is equal to #numList at that point, so temp = math.random(low, #numList) doesn’t make sense to me. Sure you didn’t want 1 there?

4. Your algorithm’s running time is O(num * (high - low + 1)), or in other words has num^2 as a lower bound. This is due to the table.remove statement which has to shift at worst #numList - 1 elements if the first element is removed.

5. An O(high - low + 1) algorithm: Add the numbers in the random range to a table, then shuffle them, and finally truncate the excess numbers. (In that case, by removing them descending order so table.remove completes in constant time and doesn’t have to shift any elements). This should be sufficient if high - low + 1 is close to num, if high - low + 1 is much larger than num it’s probably better to use:

6. O(~num) or O(num * log2(num)) algorithm depending on set type chosen: Generate a number from low to high. See if it was already generated (can be done in amortized constant time by setting up a “hash table” where such numbers are the keys and = true the values). If it’s unique, then add to output table and hash table. Jump to start unless output table is full (contains num elements).

7. You can have my shuffling implementation:

[code]function shuffle(table, lower, upper)
if lower < upper then
local i = math.random(lower, upper)
local tmp = table[lower]
table[lower] = table[i]
table[i] = tmp

return shuffle(table, lower + 1, upper)
end
end
[/code] [import]uid: 58849 topic_id: 18726 reply_id: 71965[/import]

[captain_cowell]

Thanks for the response!

1. Good point here. I didn’t do much error checking.

2. Valid concern. The only reason I used the t[#t+1] = value method in lieu of table.insert is because this guide said that it’s faster that way. Not sure the reasoning behind it, but I took the author’s word for it.

3. I used temp = math.random(low, #numList) to snag an index for the array. So, the first go around, #numList will be equal to high. After an item is removed from numList, the indices shift. I tested the algorithm several times and I got valid output every time, so I think the algorithm works logic-wise (but I’m well aware proving that it works ~50 times isn’t a proof at all x)).

4. I don’t know why I completely overlooked the run-time of table.remove. That’s an excellent point and I definitely see the O(n^2) now.

5. Excellent suggestion. I think I will go this route.

6. Sadly, this is what I was trying to go for in the first place by attempting to make a sort-of hash-table out of numList and simply pulling things out of it. My logic was to have the random number generator generate between low and the end of the numList, take the value for that index and stash it into another array, and then pull out the value of that index based on which index was chosen. I did all this without even realizing the implications of having table.remove removing random indices and the worst-case scenario if it ends up at the beginning of the array (as previously mentioned).

7. I’m definitely taking this! It’s a really good suggestion. I appreciate it!

Thanks for your feedback!! [import]uid: 52208 topic_id: 18726 reply_id: 72034[/import]

[jonathanbeebe]

EDIT: I got around to doing some tests using os.time() and yours blew mine completely out of the water. It was at least twice as fast, and sometimes three times as fast. Therefore, I went ahead and removed mine before anyone used it Lol.

Great job! What made yours way faster is the method in which you’re eliminating the existing/taken numbers. [import]uid: 52430 topic_id: 18726 reply_id: 72051[/import]

[me7]

Regarding 2): Fair point, I haven’t measured the difference.

Regarding 3) again, I know you’re computing an index. What I debate is whether “low” is the lower bound for random index. Consider what happens if you call randomsNonRepeat(200, 300, 100). I don’t know what happens when lower bound is less than upper bound for math.random(), but it surely isn’t what you intend. #numList will not be equal to high after the setup loop if low is different from 1.

If you decided to replace the whole function it’s a moot point, but it’s always good to find out why things may not have been working correctly. [import]uid: 58849 topic_id: 18726 reply_id: 72078[/import]

[captain_cowell]

Ohhhh. Yeah I completely see what you’re saying now. A 1 in place of low would make more sense so that it would always start at the beginning of the array instead of further ahead etc. Totally get it now. Whoops

But yeah, moot point. And thanks again for your shuffling implementation [import]uid: 52208 topic_id: 18726 reply_id: 72173[/import]

[Naomi]

So… @captain_cowell, what might be the final version of the function that returns the random list of numbers with no repeats? I could really use this right now…

Naomi [import]uid: 67217 topic_id: 18726 reply_id: 105418[/import]

[captain_cowell]

Naomi, I pretty much just used me7’s implementation, it’s pretty straight forward. All you have to do is populate a table with numbers that don’t repeat and use the shuffle function on it. Example:

[lua]–me7’s shuffle implementation
function shuffle(table, lower, upper)
if lower < upper then
local i = math.random(lower, upper)
local tmp = table[lower]
table[lower] = table[i]
table[i] = tmp

return shuffle(table, lower + 1, upper)
end
end
local someTable = {}

–Populate the table with numbers 1-10
for i=1, 10 do
someTable[#someTable+1] = i
end

–Shuffles the table
shuffle(someTable,1,#someTable)[/lua] [import]uid: 52208 topic_id: 18726 reply_id: 105518[/import]

[toby2]

I’ve found this shuffle function to be much* faster:

[lua]function shuffle(t)
local j
local r = math.random
for i = #t, 2, -1 do
j = r(i)
t[i], t[j] = t[j], t[i]
end
return t
end[/lua]

* By “much” I mean shuffling a million-member table goes from 1 second to .7 seconds. [import]uid: 44647 topic_id: 18726 reply_id: 105523[/import]

[Naomi]

@captain_cowell (and @me7), thank you!

@toby2, it’s even more condensed and abstract – I’d need to puzzle this one out somehow later.

Cheers,
Naomi [import]uid: 67217 topic_id: 18726 reply_id: 105541[/import]

[mtindall89]

I’m trying to do this with a group of images.

 --function to bring in images   
function storeImage()  
 local i=1; --iterator  
  
 while i\<28 do  
 local img=display.newImage(mySheet, i);  
 i = i + 1;  
 imgs:insert(img);   
 imgs[i] = img;  
 end  
end  
  
--function to randomize the images  
function randomize(group, lower, upper)  
 if lower \< upper then  
 local i = math.random(lower, upper);  
 local tmp = group[lower];  
 group[lower] = group[i];  
 group[i] = tmp;  
  
 return randomize(group, lower + 1, upper);  
 end  
end  

when I display the group on the screen after this they are still in the original order and I can’t figure out why. [import]uid: 228819 topic_id: 18726 reply_id: 144238[/import]

[mtindall89]

I’m trying to do this with a group of images.

 --function to bring in images   
function storeImage()  
 local i=1; --iterator  
  
 while i\<28 do  
 local img=display.newImage(mySheet, i);  
 i = i + 1;  
 imgs:insert(img);   
 imgs[i] = img;  
 end  
end  
  
--function to randomize the images  
function randomize(group, lower, upper)  
 if lower \< upper then  
 local i = math.random(lower, upper);  
 local tmp = group[lower];  
 group[lower] = group[i];  
 group[i] = tmp;  
  
 return randomize(group, lower + 1, upper);  
 end  
end  

when I display the group on the screen after this they are still in the original order and I can’t figure out why. [import]uid: 228819 topic_id: 18726 reply_id: 144238[/import]

[mtindall89]

I’m trying to do this with a group of images.

 --function to bring in images   
function storeImage()  
 local i=1; --iterator  
  
 while i\<28 do  
 local img=display.newImage(mySheet, i);  
 i = i + 1;  
 imgs:insert(img);   
 imgs[i] = img;  
 end  
end  
  
--function to randomize the images  
function randomize(group, lower, upper)  
 if lower \< upper then  
 local i = math.random(lower, upper);  
 local tmp = group[lower];  
 group[lower] = group[i];  
 group[i] = tmp;  
  
 return randomize(group, lower + 1, upper);  
 end  
end  

when I display the group on the screen after this they are still in the original order and I can’t figure out why. [import]uid: 228819 topic_id: 18726 reply_id: 144238[/import]

[mtindall89]

I’m trying to do this with a group of images.

 --function to bring in images   
function storeImage()  
 local i=1; --iterator  
  
 while i\<28 do  
 local img=display.newImage(mySheet, i);  
 i = i + 1;  
 imgs:insert(img);   
 imgs[i] = img;  
 end  
end  
  
--function to randomize the images  
function randomize(group, lower, upper)  
 if lower \< upper then  
 local i = math.random(lower, upper);  
 local tmp = group[lower];  
 group[lower] = group[i];  
 group[i] = tmp;  
  
 return randomize(group, lower + 1, upper);  
 end  
end  

when I display the group on the screen after this they are still in the original order and I can’t figure out why. [import]uid: 228819 topic_id: 18726 reply_id: 144238[/import]