help with treasure array

Question

Hello,

Let's say I have an array with 9 elements(treasure). // I can do this
I set it up so it randomly chooses 1 of these out of the array. // I can do this too

// But now I struggle with this-
Now, the treasure pulled can't go back in. But each time the array is accessed it needs to pull randomly from the remaining
elements until they are all gone. How do I set this up?

THanks.

Answer 1

Each time you choose one of the elements change that element to indicate it is now empty.  Something like putting a 0 there or changing it to an empty string. 

If the random chooser chooses an empty item just make it choose again.

Answer 2

That is not as simple a problem as it sounds, and is a traditional coding problem with a long legacy.

For short arrays like your 9 element example, an efficient solution is to use an index array of pointers (indexArray) to each element in the original array (treasure). You generate a random number from 0 to 1 less than the count of pointers left in indexArray. Save the indexed pointer and copy the remaining pointers after it up one slot. Now indexArray is one element smaller. Continue until you have one element left which is your last. This still allows you to directly index an element with the randomly generated index, but gets significantly slower for larger arrays.

For longer sets of objects, you need to use a shuffling algorithm on your indexArray. You can find out more about those in this Wikipedia entry .

I hope that helps.