Starting with a 10x10 array how do I choose 10 random sites

Question

I am trying to write C code to randomly select 10 random sites from a grid of 10x10. The way I am considering going about this is to assign every cell a random number between zero and RAND_MAX and then picking out the 10 smallest/largest values. But I have very little idea about how to actually code something like that :/

I have used pseudo-random number generators before so I can do that part.

Answer 1

Just generate 2 random numbers between 0 and 9 and the select the random element from the array like:

arr[rand1][rand2];

Do that 10 times in a loop. No need to make it more complicated than that.

Answer 2

To simplify slightly, treat the 10x10 array as an equivalent linear array of 100 elements. Now the problem becomes that of picking 10 distinct numbers from a set of 100. To get the first index, just pick a random number in the range 0 to 99.

int hits[10];  /* stow randomly selected indexes here */
hits[0] = random1(100);  /* random1(n) returns a random int in range 0..n-1 */

The second number is almost as easy. Choose another number from the 99 remaining possibilities. Random1 returns a number in the continuous range 0..99; you must then map that into the broken range 0..hits[0]-1, hits[0]+1..99.

hits[1] = random1(99);
if (hits[1] == hits[0]) hits[1]++;

Now for the second number the mapping starts to get interesting because it takes a little extra work to ensure the new number is distinct from both existing choices.

hits[2] = random1(98);
if (hits[2] == hits[0]) hits[2]++;
if (hits[2] == hits[1]) hits[2]++;
if (hits[2] == hits[0]) hits[2]++; /* re-check, in case hits[1] == hits[0]+1 */

If you sort the array of hits as you go, you can avoid the need to re-check elements for uniqueness. Putting everything together:

int hits[10];
int i, n;
for (n = 0; n < 10; n++) {
    int choice = random1( 100 - n );  /* pick a remaining index at random */
    for (i = 0; i < n; i++) {
        if (choice < hits[i])  /* find where it belongs in sorted hits */
            break;
        choice++;  /* and make sure it is distinct *
                   /* need ++ to preserve uniform random distribution! */
    }
    insert1( hits, n, choice, i );
            /* insert1(...) inserts choice at i in growing array hits */
}

You can use hits to fetch elements from your 10x10 array like this:

array[hits[0]/10][hits[0]%10]

Answer 3

There is a subtle bug in hjhill's solution. If you don't sort the elements in your list, then when you scan the list (inner for loop), you need to re-scan whenever you bump the choice index (choice++). This is because you may bump it into a previous entry in the list - for example with random numbers: 90, 89, 89.

The complete code:

int hits[10];
int i, j, n;
for (n = 0; n < 10; n++) {
    int choice = random1( 100 - n );  /* pick a remaining index at random */
    for (i = 0; i < n; i++) {
        if (choice >= hits[i]) {   /* find its place in partitioned range */
            choice++;
            for (j = 0; j < i; j++) {   /* adjusted the index, must ... */
                if (choice == hits[j]) {  /* ... ensure no collateral damage */
                    choice++;
                    j = 0;
                }
            }
        }
    }
    hits[n] = choice;
}

I know it's getting a little ugly with five levels of nesting. When selecting just a few elements (e.g., 10 of 100) it will have better performance than the sorting solution; when selecting a lot of elements (e.g., 90 of 100), performance will likely be worse than the sorting solution.

Answer 4

for (int i = 0; i < 10; i++) {
    // ith random entry in the matrix
    arr[rand() % 10][rand() % 10];
}

Answer 5

Modified this from Peter Raynham's answer - I think the idea in it is right, but his execution is too complex and isn't mapping the ranges correctly:

To simplify slightly, treat the 10x10 array as an equivalent linear array of 100 elements. Now the problem becomes that of picking 10 distinct numbers from a set of 100.

To get the first index, just pick a random number in the range 0 to 99.

int hits[10];  /* stow randomly selected indexes here */
hits[0] = random1(100);  /* random1(n) returns a random int in range 0..n-1 */

The second number is almost as easy. Choose another number from the 99 remaining possibilities. Random1 returns a number in the continuous range 0..99; you must then map that into the broken range 0..hits[0]-1, hits[0]+1..99.

hits[1] = random1(99);
if (hits[1] >= hits[0]) hits[1]++;

Note that you must map the complete range of hits[0]..98 to hits[0]+1..99

For another number you must compare to all previous numbers, so for the third number you must do

hits[2] = random1(98);
if (hits[2] >= hits[0]) hits[2]++;
if (hits[2] >= hits[1]) hits[2]++;

You don't need to sort the numbers! Putting everything together:

int hits[10];
int i, n;
for (n = 0; n < 10; n++) {
    int choice = random1( 100 - n );  /* pick a remaining index at random */

    for (i = 0; i < n; i++)
        if (choice >= hits[i])
            choice++;

    hits[i] = choice;
}

You can use hits to fetch elements from your 10x10 array like this:

array[hits[0]/10][hits[0]%10]

Answer 6

If you want your chosen random cells from grid to be unique - it seems that you really want to construct random permutations. In that case:

• Put cell number 0..99 into 1D array
• Take some shuffle algorithm and toss that array with it
• Read first 10 elements out of shuffled array.

Drawback: Running time of this algorithm increases linearly with increasing number of cells. So it may be better for practical reasons to do as @PaulP.R.O. says ...