Mode aléatoire sans remise

Faire une sélection aléatoire en programmation est relativement simple. On délimite l’étendue et avec une fonction pseudo-aléatoire, on demande un nombre borné par cette étendue.

Par exemple, pour obtenir un nombre entre 0 et 9, il suffit d’appeler la fonction rand() et de faire le modulo sur 10.

nombreAleatoire = rand() % 10;

Lorsque l’on désire que les nombres soient sans remise, c’est plus compliqué. Un mode sans remise, c’est comparable au boulier de la loto. Lorsque le numéro est utilisé, il ne peut plus ressortir.

Mon premier algorithme fut de créer un tableau d’entiers, de la dimension de mon tirage ( disons 10 pour continuer l’exemple) avec tous les éléments à zéro. Lorsqu’un élément était utilisé, je plaçais la valeur dans la case correspondante à 1. Si la case était déjà à 1, alors je retirais jusqu’à ce que j’obtienne un nombre dont la case du tableau était toujours à zéro. Je devais aussi m’assurer qu’il restait des cases à 0 pour continuer, sinon je redémarrais le tirage avec tous à zéro de nouveau.

Ce qui me dérange de cet algorithme, c’est la perte de temps lorsqu’il y a des tirages multiples pour trouver une valeur jamais encore utilisée. Plus le nombre de cases à 0 diminue, plus ça demande des tirages pour obtenir un nouveau nombre.

Mon nouvel algorithme est basé sur les échanges de valeurs dans les tris. Ainsi, l’algorithme démarre avec un tableau dont le contenu des cases correspond à l’index de la case. Puis lorsqu’une valeur est tirée, la valeur de la case est prise, puis échangée pour la valeur de la dernière case du tableau. Aussi, une variable qui indique la dimension du tableau est diminuée. Cette variable indique l’étendue recherchée. Lorsque cette variable arrive à 0, l’algorithme redémarre. Voici ce que ça donne en code, pour notre exemple.

#define _RAND_SIZE 10
uint8_t size = 0;
uint8_t valeurs[_RAND_SIZE];

void rand_init()
{
  for( int i = 0 ; i < _RAND_SIZE ; i++ )
     valeurs[i] = i;
  size = _RAND_SIZE; 
}

uint8_t rand_next()
{
  uint8_t index = 0; 
  uint8_t val = 0;
  if(size==0)
    rand_init();
  
  if(size)
  {
    index = rand() % size;
    val = values[index];
    values[index] = values[size-1];
    size--;    
  }
  return val;
}

Il suffit d’appeler la fonction rand_next() pour obtenir un nombre aléatoire sans remise sur l’étendue spécifiée par _RAND_SIZE.

Cet algorithme est plus stable en performance, car son temps d’exécution est le même sauf lors de l’initialisation.

Contactez-moi si vous avez une version encore plus efficase.