[vox-tech] shuffling arrays in C?

[Peter Jay Salzman]

begin Alexandra Thorn <amthorn@ucdavis.edu> 
> 
> I've been looking around for a C library function that will shuffle the
> elements of an arbitrarily long array.  I'd been hoping to turn up
> something that would randomly shuffle the elements of an array.  The array
> that I want to shuffle is made up of a class of structs that I've created.
> 
> A few hours of googling and fiddling with the man pages hasn't shed too
> much light on the issue

after a few hours, any solution is better than googling!   (-:

here's some code i quickly whipped up.   it's not the best code you can
write, but i just wanted to show an algorithm.  there are many
permutations you can make on the same algorithm; some better than
others.

i apologize if there's a mistake here.  i ran it once to make sure the
output looked sane.   looked random to me.   (-:


pete


ps- some newlines in case you don't want an answer right away.

















#include <stdio.h>
#include <stdlib.h>
unsigned int SeedRandomGenerator(void);
int Irand(int low, int high);

/* Example of shuffling an integer array.  We are going to take elements of
 * of from[], shuffle them, and place them into to[].   We're also going to
 * use another array, been_there[] to keep track of which elements of to[]
 * are free to accept an element of to[].
 *
 * There are many many ways to optimize this code, but this is simply an
 * example of the algorithm.
 */




int main(void)
{

	int n = 5;
	int i, from[n], to[n], been_there[n], myrand;
	unsigned int seed;


	/* Seed the random number generator */
	seed = SeedRandomGenerator();
	printf("seed is %u\n", seed);
	

	/* initialize from[] and been_there[].   if been_there[j] == 0, then
	 * we haven't put anything in to[j].   if been_there[j] == 1, then
	 * we've already put something in to[j].
	 */
	for (i=0; i<n; ++i) {
		from[i] = i;
		been_there[i] = 0;
	}


	/* Loop over each element of from[]. */
	for (i=0; i<n; ++i)
	{

		// Pick one of the empty slots of to[].
		do {
			myrand = Irand(0, n-1);
		} while (been_there[myrand] == 1);

		// Make a note that this element of to[] has been filled
		been_there[myrand] = 1;
		
		// Switch the elements
		to[myrand] = from[i];
	}

	// Print the results side by side.
	for (i=0; i<n; ++i)
		printf("%d   %d\n", from[i], to[i]);

	return 0;
}



/*  Seed the random number generator
 */
unsigned int SeedRandomGenerator(void)
{  
	FILE *fp;
	unsigned int seed;
	size_t retval;  

	if((fp = fopen("/dev/random", "r")) == NULL) {
		fprintf(stderr, "Can't open /dev/random for reading.");
		exit(0);
	}

	retval = fread(&seed, 1, sizeof(unsigned int), fp);

	if (retval != sizeof(unsigned int)) {
		fprintf(stderr, "SeedRandomGenerator: fread wanted %d but got %d",
			sizeof(unsigned int), retval);
		exit(0);
	}

	fclose(fp);

	srand(seed);
	return(seed);
}



/*  Returns an integer between high and low (inclusive)
 */
int Irand(int low, int high)
{
	return low + (int)( (double)(high-low+1) * rand()/(RAND_MAX + 1.0) );
}