Randomly permute a list of integers

[Michael McGarry]

Hi,

Please excuse me if this is not the right forum for this question. I
would like to create a random permutation of a list of numbers. How can
I do this in C?

I was just going to draw a number from 1 to n. n is the number of items
in the list and place the items in a new list in the order that their
index is drawn from the random number generator. Is there a library
function to do this?

Regards,

Michael

 

[Eric Sosman]

Hi,

Please excuse me if this is not the right forum for this question. I
would like to create a random permutation of a list of numbers. How can
I do this in C?

I was just going to draw a number from 1 to n. n is the number of items
in the list and place the items in a new list in the order that their
index is drawn from the random number generator. Is there a library
function to do this?

This is Question 13.19 in the comp.lang.c Frequently
Asked Questions (FAQ) list

http://c-faq.com/

 

[dcorbit]

Hi,

Please excuse me if this is not the right forum for this question. I
would like to create a random permutation of a list of numbers. How can
I do this in C?

I was just going to draw a number from 1 to n. n is the number of items
in the list and place the items in a new list in the order that their
index is drawn from the random number generator. Is there a library
function to do this?

It is trivial to make it. There are quality bugs in the code below.

#include <stdlib.h>

void shuffle(int *arr, int arr_size)
{
int tmp;
size_t i;
for (i = 0; i < arr_size; i++) {
int rval = rand() % arr_size;
tmp = arr;
arr = arr[rval];
arr[rval] = tmp;
}
}

#ifdef UNIT_TEST

#include <stdio.h>

typedef enum suite {
club=1, heart=2, diamond=4, spade=8
} suite;

typedef enum face {
deuce = 16, trey=32, four=64, five=128, six=256, seven=512,
eight=1024,
nine=2048, ten=4096, jack=8192, queen=16384, king=32768, ace=65536
} face;

int dequeue[52];

void decipher_face(int input)
{
switch ((input >> 4) << 4) {
case deuce:
printf("deuce ");
break;
case trey:
printf("trey ");
break;
case four:
printf("four ");
break;
case five:
printf("five ");
break;
case six:
printf("six ");
break;
case seven:
printf("seven ");
break;
case eight:
printf("eight ");
break;
case nine:
printf("nine ");
break;
case ten:
printf("ten ");
break;
case jack:
printf("jack ");
break;
case queen:
printf("queen ");
break;
case king:
printf("king ");
break;
case ace:
printf("ace ");
break;
default:
printf("unknown ");
break;
}
}

void decipher_suite(int input)
{
switch (input & 0xF) {
case club:
puts("of clubs.");
break;
case heart:
puts("of hearts.");
break;
case diamond:
puts("of diamonds.");
break;
case spade:
puts("of spades.");
break;
default:
puts("unknown ");
break;
}
}

int main(void)
{
suite s_index;
face f_index;
size_t index;
int where = 0;
/* Make the list... */
puts("\nMake the list...");
for (s_index = club; s_index <= spade; s_index<<=1)
for (f_index = deuce; f_index <= ace; f_index<<=1) {
dequeue[where++] = (size_t) s_index + (size_t) f_index;
}

/* Dump the original list */
puts("\nDump the original list...");
for (index = 0; index < sizeof dequeue / sizeof dequeue[0];
index++)
{
decipher_face(dequeue[index]);
decipher_suite(dequeue[index]);
}
/* Shuffle the list... */
puts("\nShuffle the list...");
shuffle(dequeue, sizeof dequeue / sizeof dequeue[0]);

/* Dump the shuffled list */
puts("\nDump the shuffled list...");
for (index = 0; index < sizeof dequeue / sizeof dequeue[0];
index++)
{
decipher_face(dequeue[index]);
decipher_suite(dequeue[index]);
}
return 0;
}
#endif

 

[Eric Sosman]

Hi,

Please excuse me if this is not the right forum for this question. I
would like to create a random permutation of a list of numbers. How can
I do this in C?

I was just going to draw a number from 1 to n. n is the number of items
in the list and place the items in a new list in the order that their
index is drawn from the random number generator. Is there a library
function to do this?

It is trivial to make it. There are quality bugs in the code below.
[...]

"Quality bugs" -- How do they differ from plain old "bugs?"

See the FAQ; the solution given there is just as short, just
as simple, and doesn't introduce bias (beyond whatever is provided
by the underlying random number generator, that is).

 

[Michael McGarry]

Cool. I was not expecting there to have been something in the FAQ. I am
pleasantly surprised.

Thank you very much,

Michael

 

[Eric Sosman]

Cool. I was not expecting there to have been something in the FAQ. I am
pleasantly surprised.

Ah, Grasshopper, much to learn you have yet. Yours to
command is the deep wisdom of the FAQ -- but only if you can
first wisdom what it is to command imagine. (Snort.) And
only if you can first read. (Snicker.)

"A day without the FAQ is like a day without getting your
tonsils ripped out by Dan Pop."

 

[dcorbit]

Hi,

Please excuse me if this is not the right forum for this question. I
would like to create a random permutation of a list of numbers. How can
I do this in C?

I was just going to draw a number from 1 to n. n is the number of items
in the list and place the items in a new list in the order that their
index is drawn from the random number generator. Is there a library
function to do this?

It is trivial to make it. There are quality bugs in the code below.
[...]

"Quality bugs" -- How do they differ from plain old "bugs?"

It is introduced/left in as an exercise for the reader.

See the FAQ; the solution given there is just as short, just
as simple, and doesn't introduce bias (beyond whatever is provided
by the underlying random number generator, that is).

That fixes one of them.