Expert: Joseph Moore - 7/9/2009

Question
Hello,
Can you teach me how to
select one element from an array via random order
then finally all the elements of that array are used(selected) once.
For example,there is an array
{ 2,4,6,8 }
I may need the following selection.
2,6,8,4    or
4,8,6,2     and so on.
How to do this in C?
I also use TCL.
If you can program this in TCL
I will be grateful to this.

Answer
I'm sorry, I'm not familiar with TCL, so I can't help you with the TCL version of this.  The C version, though, is easy enough.

There are a few ways to implement this, some better than others.  Probably the best way would be to write a linked-list and use that as a storage medium for the numbers to be grabbed in random order.  Then you can get a random number between 0 and the size of the linked list and simply take that element, write it into a new array (or list), and remove it from the original list.  In this manner, every time you use a number, it's removed from the list, and, assuming the list keeps its current size, you can simply generate a new random number with the same method and be guaranteed to get a different, random piece from the array.

The faster (implementation-wise) way to do this would be to simply set up an array that stores which indices have already been used, and keep generating a random number until it falls on an un-used index.  This is the method I went with because it's faster to implement.  If this were production code, I surely would have used a linked list.  Here's the code for the method I implemented:

   #include <stdlib.h>
   #include <time.h>

   int randRange(int _nMin, int _nMax)
   {
       return (int)((double)rand() / ((double)RAND_MAX + 1) * (_nMax - _nMin) + _nMin);
   }

   #define ARRAY_SIZE 4
   void main()
   {
       int myArray[ARRAY_SIZE] = { 2, 4, 6, 8 };
       int isUsed[ARRAY_SIZE] = { 0 };
       int outArray[ARRAY_SIZE];
       int iLoopCounter = 0;

       srand((unsigned int)time(NULL));

       for (iLoopCounter = 0; iLoopCounter < ARRAY_SIZE; ++iLoopCounter)
       {
           int nRand;
           do
           {
               nRand = randRange(0, ARRAY_SIZE);
           } while (isUsed[nRand]);

           outArray[iLoopCounter] = myArray[nRand];
           isUsed[nRand] = 1;
       }

       for (iLoopCounter = 0; iLoopCounter < ARRAY_SIZE; ++iLoopCounter)
       {
           printf("Array index %d: %d\n", iLoopCounter, outArray[iLoopCounter]);
       }
   }

The built-in rand function in C is generally poorly implemented, but it works for simple random operations.  If you need a better, more random rand function, there are plenty available on the web.  Also, note the line:

   srand((unsigned int)time(NULL));

This seeds the random number generator.  If you do not seed the generator, it will generate the same output every time.  This is handy for debugging purposes, terrible for random number generating purposes.  Often what we do in game development is seed the random number generator each time as we should, but output the seed every time we run, so that if we run into a bug, we can manually set the seed to be the same as we used when the bug was encountered.  In this way, we can control the random number generator to better reproduce bugs.

Very quickly, I'll give you some pseudo code for the linked-list implementation.

   for each element in the array
       push element into list
   while list is not empty
       generate random number from 0 to list size - 1
       iterate through list based on random number
       copy list element into output array
       remove element from list

OK, that about sums it up.  If you have any questions about any of this, please, do not hesitate to ask.  I hope you find this answer helpful.