Random Permutation Generation

Question

I am having a hard time understand this code example out of my text book. I hope someone can better explain a part of this code then my book. I am sorry for the lack of comments in this program so I will try my best to be very specific in what I am asking. Ok has the title suggest this program is a "Random Permutation Generation". Where I get confused in the code is in the function called bldPerm()

Function bldPerm():

    void bldPerm(int randNos[])
{
    int oneRandno;
    int haveRand[ARY_SIZE] = { 0 };

    for (int i = 0 ; i < ARY_SIZE; i++)
    {
        do
        {
            oneRandno = rand() % ARY_SIZE;
        } while (haveRand[oneRandno] == 1);
        haveRand[oneRandno] = 1;
        randNos[i] = oneRandno;
    }
    return;
}

I don't understand how and why the do while loop while(haveRand[oneRandno]) == 1; checks the array by comparing it to 1. Then what confuses me is that haveRand[oneRandno] = 1; is set to one in that element. Then that element being "1" is set to randNos[i] = oneRandno; and returns other numbers other then 1. The program works out of my book and does print out other numbers then 1 yet I just can't see how it works. I have been trying to warp my head around this what I am sure is a simple thing... yet I don't get it. So my question is can anyone explain what is going on in this function in detail and how it works?

FULL CODE:

#define _CRT_SECURE_NO_WARNINGS
#define ARY_SIZE 20
#include <stdio.h>
#include <stdlib.h>

void bldPerm(int randNos[]);
void printData(int data[], int size, int linesSize);

int main(void)
{
    int randNos[ARY_SIZE];

    printf("Begin Random Permutation Generation\n");
    bldPerm(randNos);
    printData(randNos, ARY_SIZE, 10);

    return 0;
}


void bldPerm(int randNos[])
{
    int oneRandno;
    int haveRand[ARY_SIZE] = { 0 };

    for (int i = 0 ; i < ARY_SIZE; i++)
    {
        do
        {
            oneRandno = rand() % ARY_SIZE;
        } while (haveRand[oneRandno] == 1);
        haveRand[oneRandno] = 1;
        randNos[i] = oneRandno;
    }
    return;
}
void printData(int data[], int size, int linesSize)
{
    int numPrinted = 0;

    printf("\n");
    for (int i = 0; i < size; i++)
    {
        numPrinted++;
        printf("%2d ", data[i]);
        if (numPrinted >= linesSize)
        {
            printf("\n");
            numPrinted = 0;
        }
    }
    printf("\n");
    return;
}

Answer 1

I went through the code and wrote some comments with the code, i hope that clears it up.

void bldPerm(int randNos[]) // here you give an array of random numbers that is empty
{
    // declare an int to store the randomly generated number
    int oneRandno;

    // initialize an array to store random numbers of size ARY_SIZE
    int haveRand[ARY_SIZE] = { 0 };

    // now loop while i is smaller then ARY_SIZE and increment i
    for (int i = 0 ; i < ARY_SIZE; i++)
    {
        // here do generate the random number
        do
        {
            // oneRandno will ALWAYS be between -1 and ARY_SIZE
            // or i.o.w. from 0 to ARY_SIZE - 1
            oneRandno = rand() % ARY_SIZE;
        } 
        // because the numbers have to be unique, if oneRandno
        // was already generated loop again
        while (haveRand[oneRandno] == 1);

        // Set to 1 because the next iteration oneRandno could have the same value,
        // however very unlikely because rand() has a period of at least 2^32 which 
        // gives you enough room to have it generate a whole lot of numbers before 
        // it generates the same number again. So basically the while loop will 
        // never loop and act like a glorified if statement.
        // and that the values in randNos should unique, if oneRandno has the 
        // same value the do while loop will iterate once more 
        // and generate another oneRandno
        haveRand[oneRandno] = 1;

        // finally store the uniquely generated number
        randNos[i] = oneRandno;

        //go to the next iteration
    }
    return;
}

Answer 2

We want to fill an array with a random permutation of the numbers 0,...,ARY_SIZE-1. This means these number in a completely random ordering.

void bldPerm(int randNos[]) {
    int oneRandno;

We keep an array called haveRand which indicates if the number i has already been chosen for our permutation. If the number is chosen haveRand[i] will be set to 1. At the beginning no number is chosen, so we initialize it with 0.

    int haveRand[ARY_SIZE] = { 0 };

For each position in our output array we randomly select one of the numbers which have not been selected yet.

    for (int i = 0 ; i < ARY_SIZE; i++)
    {

Lets find a number which has not been selected yet.

        do
        {

To do this we sample any random number and call it oneRandno.

            oneRandno = rand() % ARY_SIZE;

We check if it not chosen yet. If this is the case, then haveRand[oneRandno] is 0 and the while look will finish. Otherwise we continue and try a new.

        } while (haveRand[oneRandno] == 1);

No we mark the selected number as chosen by setting haveRand[oneRandno] to 1.

        haveRand[oneRandno] = 1;

Write the chosen number to the output array.

        randNos[i] = oneRandno;
    }
}

This algorithm is actually quite bad... For example to fill the last element there is only one candidate left as all other numbers are already selected. But the while loop tries to find this number by random sampling which can take a long time.

I would recommend creating an array with numbers 0 to ARY_SIZE-1 and use the Fisher-Yates algorithm to shuffle them.