Randomly permute a list of integers

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

  1. 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
    #1
    1. Advertising

  2. Michael McGarry

    Eric Sosman Guest

    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
    #2
    1. Advertising

  3. Michael McGarry

    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;
    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
     
    , Aug 8, 2006
    #3
  4. Michael McGarry

    Eric Sosman Guest

    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
    #4
  5. 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
    #5
  6. Michael McGarry

    Eric Sosman Guest

    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
    #6
  7. Michael McGarry

    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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Yuan Zhong

    function to permute a string

    Yuan Zhong, Aug 4, 2004, in forum: C Programming
    Replies:
    2
    Views:
    452
    CBFalconer
    Aug 5, 2004
  2. Phlip
    Replies:
    17
    Views:
    237
    Rick DeNatale
    May 18, 2009
  3. kj
    Replies:
    1
    Views:
    142
  4. PerlFAQ Server

    FAQ 4.51 How do I permute N elements of a list?

    PerlFAQ Server, Feb 7, 2011, in forum: Perl Misc
    Replies:
    0
    Views:
    157
    PerlFAQ Server
    Feb 7, 2011
  5. PerlFAQ Server

    FAQ 4.51 How do I permute N elements of a list?

    PerlFAQ Server, Mar 6, 2011, in forum: Perl Misc
    Replies:
    0
    Views:
    129
    PerlFAQ Server
    Mar 6, 2011
Loading...

Share This Page