Ramdomize a array

Monkey Forums/Monkey Programming/Ramdomize a array

Lugato(Posted 2012) [#1]
Hi to all,

I have a problem related to shuffle an array containing several words, what is the best way to do this?


Amon(Posted 2012) [#2]
Use a variable!

Psuedo:
Global numberID = -1
Global MyWordArray[2]
'0 = fruit
'1 = beer
'2 = chicken
etc etc

for local xiter:int = 0 until 2
numberID = Rnd(0, 2)
MyWordArray[xiter] = numberID
Next

If MyWordArray[0] = 1
DoStuff()
End If

Don't know if this is what you want. At 3am in the morning though...it probably isn't. :)


Jesse(Posted 2012) [#3]
here is one way:
for local i:int =  0 until words.Length()
  local f:int 
  repeat
     f  = Rnd(0,words.Length()-1)
   until f <> i
   local temp:string = words[i]
   words[i] = words[f]
  words[f] = temp
next


un tested but thats the logic.


Gerry Quinn(Posted 2012) [#4]
Here's one I wrote to randomise an array of ints. I put it in my library of helpful functions. It could easily be modified to randomise an array of anything but I haven't got around to that yet.



The rand() function is my clone of MSVC rand(), it returns an integer between 0 and 32768. You can easily replace it with your preferred function.


NoOdle(Posted 2012) [#5]
Heres some code to randomise arrays of floats, strings or ints with an example of usage.




Gerry Quinn(Posted 2012) [#6]
No need to use 32768 specifically! I just mentioned it because it happens to be the upper limit of rand() and it's large compared with typical array lengths, so you can use Mod to select an element without creating serious statistical artefacts.


NoOdle(Posted 2012) [#7]
No need to use 32768 specifically!

Well I needed a number so it seemed like a logical choice!


Gerry Quinn(Posted 2012) [#8]
Well, it turned out that I needed a randomiser for object arrays too, so I created one. I had to use a class, as follows:



It works, but I was wondering if there is any way to just have a generic function rather than a slightly artificial-seeming class?

If you could downcast arrays you could write a general function for objects, but that doesn't seem to be possible.


muddy_shoes(Posted 2012) [#9]
You can write a generic class that provides a function:



I'd generally question the need to actually shuffle elements though. Randomising access is usually what is really wanted and you can do that without moving anything.


Gerry Quinn(Posted 2012) [#10]
Yeah, that makes sense, and saves you having to instantiate an ArrayRandomiser, which is the main thing that looks artificial (though the overhead is insignificant anyway).

I don't see any harm in shuffling the elements, though - aren't the true elements of an object array just pointers anyway (unlike in C/C++ where they would be real objects)? So I am not actually moving object instances, just shuffling pointers. Same would apply to strings, and to long-ints in languages that use them. Nothing big ever gets swapped.


muddy_shoes(Posted 2012) [#11]
There may be no harm for your purposes. I wasn't claiming it was an absolute evil, just that it's often a questionable strategy.

Swapping stuff (even pointers) around takes time and mutating data in place can get tricky if that data is shared. On the other hand you might be perfectly okay with messing about with your array and shuffling once and then forever after using that randomisation could be faster.

All I'm saying is that if someone came to me with that code for review I'd immediately question if shuffling in place was really the best thing to be doing.


NoOdle(Posted 2012) [#12]
You can write a generic class that provides a function:

Ahh thats how <T> works, cheers!


Gerry Quinn(Posted 2012) [#13]
Hi muddy_shoes, I was trying out yur suggestion, with the idea of making a class called 'Generic' which would hold all functions like this. The idea was that I could write for example:

Generic< Point >.Randomise( myPointArray )

...and pretend it was Monkey syntax for generic functions.

However I found it didn't work, as I got a "method cannot be accessed from here" error. To make it work I had to instantiate the class anyway, thusly:

New Generic< Point >().RandomiseArray( seq )

...which is not so pretty, so I think I will leave it the way I did it first.

As regards the question of shuffling in place, how then would you implement shuffling a deck of cards? Of course you could use integers for cards, but maybe you are implementing a simulation of a shady riverboat gambler who has extra cards up his sleeve, or marked cards or whatever!

If you shuffled a separate array of access indexes to an immutable array of cards, it seems to me you would be just adding overhead compared to shuffling the pointers, as well as making the code clunky and error-prone. Or have you a better way of doing it?


muddy_shoes(Posted 2012) [#14]
A deck of 52 cards is a trivial amount of data so issues of performance are going to be irrelevant if you're just dealing with a single player game that uses one deck. I don't see how shuffling an array of indices is more clunky and error prone than shuffling the data array but that wasn't my suggestion and the simple answer is that I wouldn't bother thinking about optimising in that situation.

Your original question was about creating a generic function so there was no indication if the array is ten elements or ten million or how the calling code intends to use it. Given that situation I would question if shuffling in place is sensible. Returning a shuffled copy is safer and offering a randomised accessor object to a shared array can be both safer and faster (depending on the usage).

As I said, it's just a question to be asked though. If you're sure that shuffling in place is what you want to do and isn't going to be a problem then it's fine.


Gerry Quinn(Posted 2012) [#15]
Your 'simple answer' isn't really an answer. How *would* you go about implementing such a deck?

Shuffling an array of indices is an added layer of indirection and for that reason is more clunky and error prone if it is unnecessary, as it often will be. Offering a randomised accessor to a shared array can also be both less safe and slower, depending on the usage. Even returning a shuffled copy is not necessarily safer given that we are dealing with objects so it will presumably be a shallow copy. If we are using it to write to objects we are affecting the original objects anyway.

Most uses of shuffling in place will be for relatively small collections: I gave a nod to this in fact when I said that RAND_MAX of 32768 will be large enough not to create serious statistical artefacts, indicating that the intended use is for arrays of no more than a hundred or so elements.


muddy_shoes(Posted 2012) [#16]
I don't see how I can make it simpler than "I wouldn't bother thinking about optimisation in that situation" and the following paragraph explaining potential reasons for thinking more about the issue in general.

As I said, it's just a question, not a statement that you're getting it wrong. If you're happy that shuffling the array in place is what you want to do then go ahead.