[vox-tech] shuffling arrays in C?

[Bill Kendrick]

On Mon, Nov 25, 2002 at 11:05:53AM -0800, Alexandra Thorn wrote:
<snip> 
> I suppose that I might be able to hack something up to randomize the order
> of an array by using strfry to scramble an array of chars corresponding to
> indices, but wanted to check if there is a better way to do this.

I don't know of anything offhand, but then again, I was the fellow who
used to write date conversion code because I didn't know there were
libraries for it.  (Well, actually, maybe there WEREN'T...  stupid SunOS
boxes :^) )

Assuming your array is simply one of pointers, like so:

  YOUR_STRUCT * your_array[N];

Shuffling that shouldn't be too hard.  I'm not the best at
randomization code (it always ends up taking longer and longer to
find slots), but here's a few ideas:


  YOUR_STRUCT * new_array[N];
  int i, new_index;


  /* Wipe the new array (could be done with memset(), which is
     much faster, but this shows you exactly what's happening) */

  for (i = 0; i < N; i++)
    new_array[i] = NULL;


  /* For each element in the old array: */

  for (i = 0; i < N; i++)
  {
    /* Pick a random slot in the new array to place the element: */

    do
    {
      new_index = (rand() % N);
    }
    while (new_array[new_index] != NULL);  /* One that's not taken! */


    /* Put the element in the new array */

    new_array[new_index] = your_array[i];
  }



That 'do...while' loop will get slower and slower and slower until its
painful, once you're down to the last few elements.  But, on fast machines
with a small array, it ain't so bad. :^)



The above is like taking every card out of a sorted deck, and placing it
nice and neatly into random positions in a grid on the floor, and then
picking all of those up.  Voila!  Random.


Another way to do it is to literally shuffle things.  The example
below is more like taking cards out two at a time and swapping them.
(Well, that's literally what's going on with the array :^) )


  int i;
  int index_1, index_2;
  YOUR_STRUCT * temp_for_swap;


  /* Shuffle for a while... */

  for (i = 0; i < SOME_SUITABLY_LARGE_NUMBER; i++)
  {
    index_1 = rand() % N;
    index_2 = rand() % N;

    temp_for_swap = your_array[index_1];
    your_array[index_1] = your_array[index_2];
    your_array[index_2] = temp_for_swap;
  }


This is pretty simple.  There's probably more elegant ways of doing
the swap, too.  Oh, and that doesn't test for if index_1 == index_2
(e.g., it swaps with itself), but hey, that doesn't matter.
It's probably minisculy faster for not doing that comparison every
iteration.



I'm sure others around here who are more L33t3 coderz will give you
some much better examples, but it's a start. ;^)


-bill!

PS - Don't forget to call srand() at some point during your program's
     initialization!