Tirage aléatoire sans doublon et différent à chaque tirage

Signaler
-
Messages postés
5574
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
8 juin 2021
-
Bonjour,

J'ai réussi à généré les nombres au hasard mais le problème est que ces nombres sommes toujours les mêmes à chaques fois que je relance le programme ce qui est problématique.
J'aimerais savoir si il y'a un moyen pour que ces nombres soit différent à chaque tirage.

4 réponses

Messages postés
16015
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
9 juin 2021
707
Messages postés
5574
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
8 juin 2021
937
Salut Yvan,

En C, la fonction rand() donne toujours la même séquence de nombres par défaut, sauf si le générateur de nombres aléatoires est initialisé avec srand() en lui passant une "graine" (le 's' est pour "seed", c'est à dire "graine") qui peut être différente à chaque lancement de l'application, le plus commun étant de l'initialiser comme ceci
srand(time(NULL));
une fois, en début de programme. Tu as un un exemple complet avec la doc suivante :

https://www.cplusplus.com/reference/cstdlib/rand/

En faisant cela, tu auras des tirages différents à chaque lancement du programme, s'il est lancé au moins avec une seconde d'intervalle (car time() renvoie un entier avec une résolution d'une seconde).

Si tu veux aussi que lorsque les tirages sont faits, un nombre tiré ne puisse pas être tiré une seconde fois, c'est un problème distinct, et tu peux t'inspirer des techniques mises en oeuvre dans les exemples postés par Whismeril pour Python.

Dal
Messages postés
562
Date d'inscription
dimanche 7 février 2016
Statut
Membre
Dernière intervention
6 juin 2021
74
Bonjour,

La première méthode Python n'est pas applicable, et la seconde est lourdingue et est rarement utilisable.
La méthode la plus simple est :
- tu tires un nombre, et tu vérifies qu'il n'est pas dans la liste des précédemment tirés sinon tu recommences.

En C++, on peut utiliser les fonctions du C mais on devrait préférer celle du C++. Ici
rand()
et
srand()
posent les problèmes:
- c'est global, donc ne marchera pas si on souhaite des séquences basées sur une graine aléatoire et d'autre non.
- le générateur aléatoire est très/trop simpliste, il ne peut pas être utilisé en crypto par exemple.
- même si on veut une séquence toute simple on risque de mal la coder. Par exemple trouver des aléatoires entre 0 et 20000 et que l'on code
x = rand() % 20001;
c'est n'importe quoi. Essaies et tu verras que les nombres entre 0 et 12766 tombent 2 fois plus souvent que ceux entre 12767 et 20000.

#include <random>
#include <vector>
#include <algorithm>

std::vector<int>  liste_aleatoire( unsigned qte, int min, int max ) {
	static std::random_device  rd;          // pour la graine
	static std::default_random_engine  gene{rd()};   // le générateur, ici un géné basique
	std::uniform_int_distribution<int>  distr(min,max); // ce que l'on veut, ici des entiers entre min et max inclus, tous équiprobables

	std::vector<int>  res;
    if ( min+qte > max+1u ) throw "c'est impossible";
	while ( qte-- ) {
		int  x = distr(gene);          // choisir un nombre en utilisant le générateur
		while ( std::find(res.begin(),res.end(),x) != res.end() ) // tant que déjà vu
			x = distr(gene); // essayer un autre
		res.push_back( x );
	}
	return  res;
}
Messages postés
5574
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
8 juin 2021
937
Salut Dalfab,

Merci de ta contribution éclairée en C++.

J'ai répondu en C. Des personnes débutantes en C postent occasionnellement dans le forum C++ et j'ai supposé que le PO faisait du C en utilisant rand() sans initialisation préalable avec srand() en raison de son indication :

"le problème est que ces nombres sommes toujours les mêmes à chaque fois que je relance le programme ce qui est problématique" (sic)

En C aussi, pour un usage "sérieux" (crypto, cahier des charges de tirages non biaisés, correctement distribués), on n'utilisera pas rand(), mais une bibliothèque comme, par exemple, ce module de la Gnu Scientific Library :

https://www.gnu.org/software/gsl/doc/html/rng.html

En tout état de cause, tu as tout à fait raison de dire que si le PO fait effectivement du C++, il ne devrait pas utiliser ces fonctions du C standard, dans la mesure où le C++ standard dispose de meilleures implémentations.
Messages postés
16015
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
9 juin 2021
707
Salut

La première méthode Python n'est pas applicable
si tu parles de celle de yg_be évidement c'est purement du python mais c'est chronologiquement la 3eme solution proposée.

Si tu parles de celle de NHenry (la première chronologiquement), c'est applicable avec une liste chainée. Et cette solution (comme la mienne) présente un avantage sur la tienne quand on veut faire de grands tirages.

Si tu veux tirer, sans doublons, tous les nombres de 1 à 1000, il va arriver un moment où le random sortira en majorité des nombres déjà tirés (sans même parler de
tu verras que les nombres entre 0 et 12766 tombent 2 fois plus souvent que ceux entre 12767 et 20000.
) , la vérification de la présence prendra un certain temps puis la nouvelle tentative aussi, bref y'a un risque non négligeable que ça pédale dans la semoule.


Evidement si le but est de tirer de petites séquence représentant un faible pourcentage de l'intervalle, ta méthode est bonne et peut-être plus rapide.
Messages postés
5574
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
8 juin 2021
937
Je suis d'accord avec toi que la méthode du mélange est intéressante et évite les nouvelles tentatives de tirages.

Il y a la méthode suivante pour faire des mélanges de ce type :

https://en.wikipedia.org/wiki/Fisher–Yates_shuffle