Cogitatio materialis est

Generate random array without repetitions in C ?

14th Dec 2013 Tags: #algorithms #c #development

Let's asume, You need to generate random numbers without repetitions. If you know the range (between 0 and N_MAX) and the count, you have many ways to implement this. The best one, in my opinion, I will show below.

The idea is deadly simple - you generate the array of nessesary numbers (structures/odjects/etc) and.. shuffle it :) For example, with Donald Knuth alghoritm ("The Art of Computer Programming", vol.2, Alg.3.4.2.P).

Here's rudimental example in C:

/**
 * Knut's shuffle example.
 * gcc -Wall -Wextra -std=gnu99 random_array.c -o random
 */

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

int rand_lim(int limit);

int main(int argc, char* argv[])
{
  int array_size = 10;
  if (argc > 1)
    array_size = atoi(argv[1]);

  if (array_size < 1) {
    printf("Usage: %s <size of array>\n", argv[0]);
    exit(1);
  }
  else
    printf("use array of %d elements\n", array_size);


  int i, j, m;
  int *a; /* just a dynamic array */

  a = (int *) malloc(array_size * sizeof(*a));
  if (NULL == a) {
    printf("Memory fails");
    exit(1);
  }

  /* init array with ints between 0..array_size */
  for (i = 0; i < array_size; ++i)
    a[i] = i;


  /* shuffle it */
  srand(time(NULL));

  for(i=0; i < array_size-1; i++)
  {
    m = i + rand_lim(array_size-i-1);
    j = a[i];
    a[i] = a[m];
    a[m] = j;
  }

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

  free(a);
  return 0;
}

/**
 * return a random number between 0 and limit inclusive.
 */
int rand_lim(int limit)
{
  int divisor = RAND_MAX/(limit+1);
  int retval;

  do { 
    retval = rand() / divisor;
  } while (retval > limit);

  return retval;
}

P.s. It is a common practice to get random number in range like

/* random int between 0 and 19 */
int r = rand() % 20;

but it is not the correct one. Actually, this is a topic for another article. In a nutshell, attempts that just use % (or, equivalently, /) to get the numbers in a range almost inevitably introduce skew (i.e., some numbers will be generated more often than others). You can read more about this here.