Non-repeating Random Values

A Programming Adventure

Random Fun

Introduction

Randomization is fun. 

It allows us the ability to model things as they occur in real-life.  Of course I realize that how randomization occurs in a computer program is not exactly 'random' but rather, 'pseudo-random'.  This presents certain problems as the random (numbers) things in the computer can be reproduced under specific conditions.  However, pseudo-randomization is 'good-enough' to give us good results.  This is where fun things can happen.

I recently wanted to use randomization but with a specific idea in mind--randomize without repeating values already received from randomization.  This is the subject of this small text.

Some Basic Info

In C, randomization is quite easy; we call a function rand() which in turns provides us with a random value from 0 to RAND_MAX; an implementation-defined value.  We can control the range of randomization by using the modulo operator: %.  This allows us flexibility to obtain a random value within a range.  For example, to obtain a random value between 1 and 20, we could write:

int random_value = rand() % 20 + 1;

random_value then receives any number between 1 and 20.  Additionally, in order to ensure that the sequence of values returned from rand() is different every time we run the program, we use a seeding value before calling rand().  A common technique is to use time() to seed the random number generator.  We can then run the program multiple times and receive a different set of random values. 

Non-Repeating

I wanted to use randomization in order to generate a set of random values from 0 to an arbitrary number but without them repeating.  For example, the following code:

int range = 10;
 srand(time(NULL));
 for(int i = 0; i < range; i++){
     printf("%i ", rand() % range + 1);
 }

Will yield values such as:

7 7 3 9 8 3 7 3 1 2

Random numbers are generated from 1-10, but values 7 and 3 repeat themselves in the sequence. Additionally, values 4, 5, 6 and 10 are not included.  This is what I wanted to avoid. 

Algorithm

The algorithm that best describes what I needed is as follows:

1. Generate a random number from 0 to N
2. Check if the random number is in an array of random values
3. If the number is in the array, go to step 1, else go to step 4
4. Store the random number in the array
5. Continue until we have processed all values within the range

This works perfectly well.  The code is as follows (a complete implementation is provided):

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

 

int main(void){

 /* set a range of random values */ 

int range = 20;

 /* random number receiver */ 
int rand_value = 0;

 /* array to receive unique-random values */ 
int rand_vals[range];

 /* init array */ 
for(int i = 0; i < range; i++){
  rand_vals[i] = -1;
 }

 /* array-index iterator */ 
int iter = 0;

 /* seed rand() */ 
srand(time(NULL));

 /* store a rand() value only if it has not already been processed */ 
while(iter != range){
     rand_value = rand() % range;
     for(int i = 0; i < range; i++){
         if(rand_value == rand_vals[i]){
             rand_value = rand() % range;
             i = -1;
             continue;
         }
     }
     rand_vals[iter] = rand_value;
     iter++;
 }
 

/* print */ 
for(int i = 0; i < range; i++){
  printf("%i ", rand_vals[i]);
}

return 0;
}

This yields a result such as:

13 15 9 4 11 6 19 12 0 10 14 3 5 8 1 2 16 18 7 17

A very cool result.  Numbers are generated randomly but ensuring they only occur once.