Generating Unique Random Numbers in an Array using

问题:

So the question is to develop a [5][5] table, each containing unique numbers from 1-100 (no duplicates)

so here's what I came up with:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    int outerLoop;
    int innerLoop;

    int board[5][5]; /* Array Name And Size*/

/* seeds the random number generator*/

srand(time(NULL));

int number;

number = rand() % 101;

/* Start a loop to generate a random integer between 1 and 100 and 
assign it into the array. The loop runs 25 times*/

for (  outerLoop = 0  ;  outerLoop <= 25  ; outerLoop++ ) /* loop 25 times*/
{
    for (  innerLoop = 0  ;  innerLoop <= 4  ; innerLoop++   ) /* <=4 due to 5
columns*/
    {
        board[outerLoop][innerLoop] = rand() % 100 + 1;
    }
    printf( "%d \n", board[outerLoop][innerLoop] );
}

So I pretty much got stuck here.I'm not really sure about this:

board[outerLoop][innerLoop] = rand() % 100 + 1;

I simply made it up :/ Any idea guys?

回答1:

What you want is a shuffle algorithm

Shuffle array in C

To get your 25 element array of unique #s from 1 to 100; just create a 100 element array with the numbers 1..100, shuffle the 1st 25 from the pool of 100, and use the 1st 25.

$ cat test.c
    #include <stdio.h>
    #include <stdlib.h>

    void shuffle(int *array, size_t array_size, size_t shuff_size)
    {   
        if (array_size > 1)  
        {   
            size_t i;
            for (i = 0; i < shuff_size - 1; i++) 
            {   
              size_t j = i + rand() / (RAND_MAX / (array_size - i) + 1); 
              int t = array[j];
              array[j] = array[i];
              array[i] = t;
            }   
        }   
    }   

  int main(int argc, char * argv[]) {
        int a[100];
        int b[5][5];
        int i,j,k=0;

        for(i=0; i<100;++i)
            a[i]=i;

        shuffle(a,100,25);

        for(i=0;i<5;++i)
            for(j=0;j<5;++j) {
                b[i][j] = a[k++];
                printf("%d ",b[i][j]);
        }
        printf("\n");
    }   

$ gcc -o test test.c

$ ./test
0 14 76 47 55 25 10 70 7 94 44 57 85 16 18 60 72 17 49 24 53 75 67 9 19 

回答2:

Think of it like a deck of 100 cards.

• Create a 100 element array holding the card numbers (1..100)
• Shuffle the array (=deck). (see @koodawg's answer and @Steve314's comment)
• "Deal" yourself the first 25 cards off the deck, into your 5x5 array.

回答3:

Just create array of boolean of size 100 : bool numberUsed[100]. Then in cycle:

1.Generate random number r
2.If numberUsed[r] is true, dont add that r anywhere and continue in loop
3.numberUsed[r] = true

Note that you need to use WHILE cycle with this approach, not FOR cycle.

回答4:

Here is some pseudo code to solve it:

• Create a "list" of length 100 containing the numbers 1...100 called "numbersAvailable"
• In your inner loop set index = (int)rand() * numbersAvailable; and the take the number numbersAvailable.get(index); and then do numbersAvailable.remove(index);

In Java creating a list is easy. If you like to stick to C you have to emulate this via arrays. (I can write down the solution, but this looks like a homework, so I leave something for you).

Note: In contrast to a trial-and-reject solution, this solution has the advantage of a fixed amount of time needed to construct the result.

回答5:

Since int board[5][5]; allocates a continuous amount of memory you can initialise it with just

for (i = 0; i < sizeof(board)/sizeof(int); i++)
    board[0][i] = rand() % 100 + 1;

Or use a double loop like you did, but then you only need to loop 5 times in the other loop, or use sizeof to set the iteration count automatically:

for (  outerLoop = 0  ;  outerLoop < sizeof(board)/sizeof(board[0])  ; outerLoop++ ) {
    for (  innerLoop = 0  ;  innerLoop < sizeof(board[0])/sizeof(board[0][0])  ; innerLoop++   ) {
        board[outerLoop][innerLoop] = rand() % 100 + 1;
    }
}

Please keep in mind that sizeof will only work on arrays in this way when the length of the array is known at compile time like it is in your example.

回答6:

C stores arrays in row-major order, i.e, the elements of row 0 comes first , followed by the elements of row 1, and so forth.

We can take advantage of this by viewing int board[5][5] as int board[5*5].

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 5

int main()
{
    int i, outerLoop = 1;
    int board[N*N];

    srand(time(NULL));

    int number;
    board[0] = rand() % 100 + 1; //initializing the first element

    while(1)
    {
            number = rand() % 100 + 1 ;

            if(outerLoop == N*N)
                break;      
            else
            {
                //Cheking the previous elements for no duplicacy
                for ( i = 0; i < outerLoop; i++)
                {
                    if(number == board[i])
                        break;
                }

                //confirming whether all the elements are checked or not and the assigning number to the array element and then increment the counter outerLoop 
                if(i == outerLoop)
                {
                    board[outerLoop] = number;
                    outerLoop++;
                }
                else
                    continue;
            }

    }

    //Printing the elements of array board[N*N]
    for (  outerLoop = 0  ;  outerLoop < N*N  ; outerLoop++ )
    {
        printf( "%d\t", board[outerLoop] );
        if(outerLoop % N == 4)
            printf("\n\n");
    }

}