# Randomly permute a list of integers

Discussion in 'C Programming' started by Michael McGarry, Aug 8, 2006.

1. ### Michael McGarryGuest

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

Michael McGarry, Aug 8, 2006

2. ### Eric SosmanGuest

Michael McGarry wrote:

> 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/

--
Eric Sosman
lid

Eric Sosman, Aug 8, 2006

3. ### Guest

"Michael McGarry" <> wrote in message
news:...
> 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;
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

, Aug 8, 2006
4. ### Eric SosmanGuest

wrote:

> "Michael McGarry" <> wrote in message
> news:...
>
>>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).

--
Eric Sosman
lid

Eric Sosman, Aug 8, 2006
5. ### Michael McGarryGuest

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

Thank you very much,

Michael

Eric Sosman wrote:
> Michael McGarry wrote:
>
> > 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/
>
> --
> Eric Sosman
> lid

Michael McGarry, Aug 8, 2006
6. ### Eric SosmanGuest

Michael McGarry wrote:
> 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."

--
Eric Sosman
lid

Eric Sosman, Aug 9, 2006
7. ### Guest

Eric Sosman wrote:
> wrote:
>
> > "Michael McGarry" <> wrote in message
> > news:...
> >
> >>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.

> --
> Eric Sosman
> lid

, Aug 11, 2006