On est parfois amené à devoir générer une suite de nombres sans doublons ; c'est à dire que si un certain nombre a déjà été tiré, il n'est pas possible de le tirer à nouveau. Les exemples sont multiples : tirer des cartes dans un tas, établir un ordre de passage aléatoire à un examen pour une liste d'étudiants, faire un diaporama aléatoire, ... bref les applications ne manquent pas.
Pour expliquer l'algo, je générerai une liste sans doublons d'entiers de 0 à
MAX ; la modification à apporter pour avoir une génération entre
MIN et
MAX étant minime, elle sera apportée tout à la fin.
Une première idée
La première idée, naïve, qu'on pourrait avoir serait de tirer un nombre au hasard, regarder si ce nombre a déjà été tiré, et en retirer un autre tant que ce nombre n'a pas été tiré.
Mais comment peut-on savoir si un nombre a déjà été tiré ?
On peut procéder ainsi : les nombres tirés sont stockés dans un tableau de taille
MAX, dans leur ordre d'apparition. La première case contiendra le premier nombre tiré, la deuxième case le deuxième, et ainsi de suite.
Lorsqu'on tire un nouveau nombre, on parcourt le tableau pour voir s'il y est déjà présent ; si c'est le cas, on ne touche pas au tableau et on recommence en tirant un nouveau nombre ; sinon, on ajoute ce nombre à la dernière case libre du tableau. Pour connaître l'indice de cette case, on peut utiliser une variable "compteur" qu'on initialisera à 0 au début, puis qu'on augmentera de 1 à chaque fois qu'on ajoute un nombre.
On a donc potentiellement un algo qui fonctionne. Maintenant, si vous avez du temps à perdre, vous pouvez l'implémenter et tester différentes valeurs de
MAX : 200, 2 000, 20 000, 200 000 ... Personnellement, ma bécane traite le cas 20 000 en une dizaine de secondes et ne s'arrête pas en temps raisonnable (inférieur à la minute) pour 200 000. C'est dommage, j'ai 200 000 candidats qui vont passer le Bac (à sable

) et je dois leur donner un ordre de passage aléatoire...
Ce qui est très long dans cette façon de faire, c'est qu'on parcourt toute la partie du tableau déjà remplie pour savoir si un nombre a été tiré. Si on pouvait connaître instantanément cette information, on gagnerait beaucoup en efficacité. L'idée est donc de la stocker dans un deuxième tableau
test : si le nombre
i a déjà été tiré, alors
test[i] est à
1, sinon il est à
0.
L'intuition nous pousse à penser que cet algo peut ne jamais s'arrêter. C'est faux ! Prenons par exemple le cas où il ne reste plus qu'un nombre à tirer : la probabilité de NE PAS tirer ce nombre au premier coup est extrêmement élevée, mais tout de même strictement inférieure à 1. Notons la p. Pour que ce nombre ne soit pas apparu au deuxième coup, il ne doit pas être sorti au premier coup, ET ne doit pas être sorti au deuxième.
Si vous avez déjà manipulé un peu de probas, vous devez savoir que la probabilité de l'événement "A ET B" est égale à la probabilité de l'événement "A" multipliée par celle de l'événement "B" (si les événements sont indépendants, ce qui est le cas). Donc ici la probabilité de "le nombre n'est pas apparu au deuxième coup" est de : p*p=p².
Et ainsi de suite, vous comprenez sans peine que la probabilité de "le nombre n'est pas apparu au n-ième coup" est de pn. Mais p est strictement inférieur à 1. Donc lorsque n devient très grand, pn devient aussi proche de 0 que l'on veut. Donc l'événement "le nombre n'apparaît jamais" a une probabilité de 0, tout pile.
En conclusion, le nombre de coups nécessaires pour avoir le dernier nombre est bien fini ; il peut en revanche être très grand.
Une approche plus efficace !
L'idée
La dernière version tourne assez rapidement (MAX=200 000 est traité chez moi en un clin d'œil), mais il subsiste deux points noirs :
- comme indiqué dans l'encadré juste au-dessus, même si le nombre de tirages est fini, il peut être très grand, ce qui prendra beaucoup de temps ;
- on a besoin d'un tableau annexe (test), ce qui prend de la place.
Pour comprendre le nouvel algo, je vais faire l'analogie avec un jeu de cartes ; remarquez que distribuer toutes les cartes aux joueurs revient à générer sans doublons toutes les cartes et les donner aux joueurs au fur et à mesure. Pour faire cela, est-ce que vous utilisez l'algo que j'ai décrit au dessus lorsque vous jouez aux cartes en famille ? Je ne pense pas (ou alors allez vite consulter un médecin, c'est grave

); non, vous
mélangez vos cartes !
C'est exactement la même idée ici. Nous allons encore avoir besoin d'un tableau (mais d'un seul cette fois). Pour l'initialiser, nous le remplissons "dans l'ordre" : à la case n° 0, on y met 0, à la n°1, on y met 1 et ainsi de suite jusqu'à
MAX. Ensuite il suffit de le mélanger.
Alors un paquet de cartes, je vois comment le mélanger, mais un tableau stocké dans la RAM, j'ai plus de mal ...
Pas de panique ! L'idée est toute simple : vous tirez un nombre aléatoire
a entre 0 et
MAX ; puis vous échangez le contenu de la case n°
0 avec la case n°
a. Et vous faites ça pour toutes les cases. Cet algo corrige bien les deux écueils que j'avais relevés à propos du premier et génère bien une suite sans doublons.
Il reste une petite broutille : pour l'instant, l'algorithme génère des entiers entre 0 et un nombre. Pour générer une suite à valeurs dans
[a,b[, il n'y a qu'une modification à faire, lors de la génération du tableau : à la case n°0, on met
a, à la case n°1, on met
a+1 et ainsi de suite. C'est tout ! Le reste du code se contentera de mélanger les cases, sans se préoccuper de leurs valeurs (il faut tout de même bien penser à tirer les valeurs dans l'intervalle
[0,b-a[ pour que les nombres tirés soient bien des indices du tableau).
L'implémentation
On pourrait écrire une fonction qui prend en argument
a et
b, les bornes de l'intervalle dans lequel on veut générer notre suite, et qui alloue un tableau, lui applique l'algo décrit au-dessus et le renvoie.
Problème : si on veut générer plusieurs suites aléatoires du même intervalle, on devra allouer et initialiser un nouveau tableau à chaque fois. Ce qui prend du temps. Et vous l'aurez remarqué, je n'aime pas en perdre !
On va donc écrire deux fonctions : une qui alloue et initialise le tableau et une qui se contente de mélanger un tableau passé en paramètre. Si on veut une nouvelle suite, il nous suffira de re-mélanger le tableau, sans avoir à le réallouer.
La première ne devrait pas vous poser de problèmes ; elle prend deux arguments entiers
a et
b qui sont les bornes de l'intervalle et renvoie un pointeur sur un tableau de taille
(b-a) contenant
{a, a+1, a+2, ..., b-1}. La voici :
Code : C | int* init_sans_doublons(int a, int b){
int taille = b-a;
int* resultat=malloc((taille)*sizeof (int));
int i=0;
// On remplit le tableau de manière à ce qu'il soit trié
for(i = 0; i< taille; i++){
resultat[i]=i+a;
}
return resultat;
}
|
Pour la deuxième, la seule difficulté se situe peut-être dans l'échange des valeurs de deux cases ; pour ce faire, on est obligé d'utiliser une variable
temp. Cette fonction prend deux arguments : un pointeur vers un tableau et la taille de celui-ci.
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13 | void melanger(int* tableau, int taille){
int i=0;
int nombre_tire=0;
int temp=0;
for(i = 0; i< taille;i++){
nombre_tire=rand_a_b(0,taille);
// On échange les contenus des cases i et nombre_tire
temp = tableau[i];
tableau[i] = tableau[nombre_tire];
tableau[nombre_tire]=temp;
}
}
|
Mais elle ne renvoie rien cette fonction !?
Effectivement, elle va directement modifier le tableau qu'on lui passe en paramètre, il n'y donc rien besoin de renvoyer !
Voilà, tout est prêt, il ne me reste plus qu'à vous donner un
main qui permet de tester ces fonctions : le programme suivant génère une suite de nombres compris entre deux nombres entrés par l'utilisateur. Note importante : la fonction
init_sans_doublons alloue un tableau,
il faut impérativement penser à libérer l'espace par la suite !
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | int main(){
// A ne pas oublier !
srand(time(NULL));
int a=0;
int b=0;
int i =0;
int* t=NULL; // Va contenir le tableau de nombres
do{
printf("Rentrez le premier nombre : ");
scanf("%d",&a);
printf("Rentrez le second, plus grand que le premier : ");
scanf("%d",&b);
}while(b<=a);
// On commence pour de vrai ici :
t=init_sans_doublons(a,b);
melanger(t,b-a);
printf("La suite aléatoire est : ");
for(i=0; i<b-a; i++){
printf("%d ",t[i]);
}
printf("\n");
// Ne pas oublier de libérer le tableau
free(t);
return 0;
}
|
Ici, j'ai choisi de passer la taille du tableau en second argument de la fonction melanger. C'est assez désagréable : on est obligé de la calculer (alors que init le fait déjà) puis de se souvenir de cette taille pour appeler cette fonction. La solution habituelle est de créer un struct qui contient deux champs : le tableau et la taille de celui-ci. init_sans_doublons renverrait alors un pointeur vers une structure de ce type, calculant la taille une fois pour toute. Et melanger prendrait alors un seul argument : (un pointeur vers) la structure considérée.
Pour des raisons de simplicité, je n'ai pas opté pour cette solution pour le tuto ; dans la vraie vie, si vous devez vous servir à de nombreuses reprises de ces fonctions, je ne peux que vous conseiller de l'implémenter.