l i n u x - u s e r s - g r o u p - o f - d a v i s
L U G O D
 
Next Meeting:
September 2: Social gathering
Next Installfest:
TBD
Latest News:
Aug. 18: Discounts to "Velocity" in NY; come to tonight's "Photography" talk
Page last updated:
2002 Nov 25 12:06

The following is an archive of a post made to our 'vox-tech mailing list' by one of its subscribers.

Report this post as spam:

(Enter your email address)
Re: [vox-tech] shuffling arrays in C?
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [vox-tech] shuffling arrays in C?



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!
_______________________________________________
vox-tech mailing list
vox-tech@lists.lugod.org
http://lists.lugod.org/mailman/listinfo/vox-tech



LinkedIn
LUGOD Group on LinkedIn
Sign up for LUGOD event announcements
Your email address:
facebook
LUGOD Group on Facebook
'Like' LUGOD on Facebook:

Hosting provided by:
Sunset Systems
Sunset Systems offers preconfigured Linux systems, remote system administration and custom software development.

LUGOD: Linux Users' Group of Davis
PO Box 2082, Davis, CA 95617
Contact Us

LUGOD is a 501(c)7 non-profit organization
based in Davis, California
and serving the Sacramento area.
"Linux" is a trademark of Linus Torvalds.

Sponsored in part by:
EDGE Tech Corp.
For donating some give-aways for our meetings.