Tableau de nombres aléatoires sans doublons.

Un algorithme rapide pour créer un tableau aléatoire sans doublons.

rand

Voir version :

Pas de dépendances

Télécharger :

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

int *tirage(int nombre, int min, int max)
{
    int *tabelems, *ret, i, indice, maxi = max - min;
    if(min >= max || nombre > maxi + 1 || nombre < 1)
        return NULL;
    tabelems = malloc((maxi + 1) * sizeof(int));
    ret = malloc(nombre * sizeof(int));
    for(i = 0; i < maxi + 1; i++)
        tabelems[i] = i + min;
    for(i = 0; i < nombre; i++){
        indice = rand() % (maxi + 1);
        ret[i] = tabelems[indice];
        tabelems[indice] = tabelems[maxi];
        maxi--;
    }
    free(tabelems);
    return ret;
}

int main()
{
    int i,j,*tab;
    int nb = 7;
    srand(time(NULL));
    for(j = 0; j < 10; j++) 
    {
        if((tab = tirage(nb, 1, 49))) 
        {
            printf("Tirage %2d :", j + 1);
            for(i = 0; i < nb; i++)
                printf("  %d", tab[i]);
            printf("\n");
            free(tab);
        }
    }
    return 0;
}



Commentaires

	Avant tout, merci à Magma pour avoir posté cet algorithme sur le site du zéro.

	C'est un algorithme fort élégant que je voulais conserver. 

	Le concept est le cas suivant : Considérons le jeu du loto : parmi 49 numéros, on en tire 7.
	Evidemment, toute la difficulté est qu'on ne veut pas tirer plusieurs fois le même.

	Algorithme bourrin
	------------------
	On fait un for sur chaque numéro à tirer, et pour chaque numéro tiré, on vérifie tous les précédents en imbriquant un while jusqu'à ce qu'on en trouve un 
	qui soit libre.
	Complexité du truc : n². Alors pour 7 numéros, ça va. Mais si je veux 1 million de numéros, la, on souffre...

	Algorithme un peu moins bourrin
	-------------------------------
	On écrit tous les nombres possibles dans un tableau. Concrètement, dans mon cas, je fais un tableau de 49 éléments, dans lequel j'écris 1,2,3,4,...,48,49
	Puis je vais swapper au random 2 éléments au hasard, et cela X fois. A la fin, on ne prend que les N éléments souhaités.
	On a un jeu de carte trier : a force d'échanger les cartes 2 par 2 au hasard, on finit par avoir un jeu mélangé.
	Mais il faut que X soit grand, voir bien plus grand que N. Complexité X donc.

	Algorithme élégant (celui présenté dans le programme)
	-----------------------------------------------------
	Pareil qu'au dessus, je prépare un tableau tab de 49 éléments : 1,2,3,4,...,48,49
	Mais cette fois, je vais créer mon tableau ret de N éléments, et le remplir dans l'ordre.
	Pour la case 0 de ret, je prends un indice dans le tableau tab, ce sera mon premier élément.
	L'astuce consiste ensuite à remplacer l'élément tiré par celui de la fin, et de réduire la taille du tableau, pour être sur de ne pas le reprendre.

	Exemple :
	Je choisis l'index 4. 
	Donc ret[0] = 4;
	Puis je mets le dernier élément (49) à la place, donc j'écrase le 4 : je suis sur que je ne le reprendrai pas.
	Le tableau devient :

	1,2,3,49,5,6,....,47,48,49

	On a deux fois 49, sauf que pour la prochaine itération, je considère le tableau avec un élément de moins, donc 1,2,3,49,5,6,....,47,48

	Nous avons un bel algo de mélange de complexité n, bien plus rapide que les autres algos du dessus.

Laissez un commentaire / post a comment