Génération de codes aléatoires uniques

Bonjour.
J'aimerais générer un nombre important de séquences alphanumériques aléatoires (de même taille, les lettres et les chiffres placés au mêmes endroits) sans doublons.
Ça, pas de souci je sais faire.

En fait, j'ai un problème d'optimisation.
L'approche naïve que j'emploie est la suivante :

1. Générer une séquence aléatoire
2. Vérifier qu'elle n'a pas déjà été générée
3. Si oui, revenir au 1.
4. Enregistrer la nouvelle séquence

En continuant tant que le quota n'est pas atteint.

Évidemment, plus ça va, plus c'est lent…
N'y aurait-il pas une approche plus rapide, plus efficace ?
Peut-être spécifique à un langage particulier ?

Si vous avez des suggestions, je suis tout ouïe.

PS: Je ne suis pas encore décidé sur le langage.
C, C++, Java, Perl, Python…

Bonjour,

Citation:

---

Envoyé par Steph_ng8

N'y aurait-il pas une approche plus rapide, plus efficace ?

---

On peut créer une relation d'ordre sur les séquences. Pour ton cas précis, on peut même créer une séquence unique à partir d'un nombre d'ordinal.

Exemple simple : Un code du genre [lettre][lettre][chiffre]

On assigne pour chaque lettre un numero de 1 à 26, et pour chaque chiffre un numéro de 0 à 9. On peut donc décrire chaque séquence possible avec ces 3 valeurs.

Si on considère A=1, B=2, ... on obtient, par exemple :

numero d'ordre (05,07,8) ---> E G 8

Pour être certain de ne pas retomber sur une séquence existante, il suffit de prendre comme prochain numéro d'ordre un numero strictement supérieur à l'actuel.

Citation:

---

Envoyé par pseudocode

On peut créer une relation d'ordre sur les séquences.

---

Il y a déjà une relation d'ordre : l'ordre lexicographique.
Ce qui revient à peu de choses à ce que tu as mis.

Citation:

---

Envoyé par pseudocode

Pour être certain de ne pas retomber sur une séquence existante, il suffit de prendre comme prochain numéro d'ordre un numero strictement supérieur à l'actuel.

---

Et comment on le « prend » ?

Citation:

---

Envoyé par Steph_ng8

Et comment on le « prend » ?

---

Au hasard. Par exemple par dichotomie.

Ah, je crois que je commence à voir où tu veux en venir.
Au lieu de générer aléatoirement tous les caractères de la séquence, puis de vérifier si elle n'a pas déjà été générée, tu proposes de tous les mettre à plat et de « choisir » le numéro X, puis le numéro Y, etc.
Enfin de construire la séquence à partir du numéro (d'ordre) générer.

Ça permet entre autres de ne faire qu'un seul tirage pseudo-aléatoire, puis si la vérification est nécessaire, elle se fait sur un entier, et pas sur une séquence de caractères.

Si j'ai bien compris, ça me paraît une très bonne idée. :ccool: ;)

Reste à s'assurer que tous les numéros d'ordre sont représentables…

Citation:

---

Envoyé par Steph_ng8

Ah, je crois que je commence à voir où tu veux en venir.
Au lieu de générer aléatoirement tous les caractères de la séquence, puis de vérifier si elle n'a pas déjà été générée, tu proposes de tous les mettre à plat et de « choisir » le numéro X, puis le numéro Y, etc.
Enfin de construire la séquence à partir du numéro (d'ordre) générer.

---

Oui, c'est ca.

Citation:

---

Reste à s'assurer que tous les numéros d'ordre sont représentables…

---

Il le sont forcément (ton nombre d'élément est fini). Par contre, il est vrai que ce n'est pas forcément trivial de passer d'un numero d'ordre à l'élément correspondant.

Si on reprend l'exemple [lettre1][lettre2][chiffre]

en posant a=0, b=1, ..., z=25

alors un numero d'ordre peut être

numordre = #lettre1*26*10 + #lettre2*10 + #chiffre

et inversement

#chiffre = numordre % 10
#lettre2 = (numordre-chiffre)/10 % 26
#lettre3 = (numordre-chiffre-#lettre2*10)/(10*26) % 26

(aux erreurs de calculs près, en cet heure tardive)

Citation:

---

Ça permet entre autres de ne faire qu'un seul tirage pseudo-aléatoire, puis si la vérification est nécessaire, elle se fait sur un entier, et pas sur une séquence de caractères.

---

En procédant par dichotomie pour les tirages, tu peux te passer de la vérification. Il suffit de tirer un numero d'ordre dans un des intervalles

Par exemple, si on imagine 100 numeros d'odre possible:
>intervalles : [0,100[
tirage : 33

->intervalles : [0,33[ & ]33,100[
tirage : 54

->intervalles : [0,33[ & ]33,54[ & ]54,100[
...

Citation:

---

Envoyé par pseudocode

Citation:

---

Envoyé par Steph_ng8

Reste à s'assurer que tous les numéros d'ordre sont représentables…

---

Il le sont forcément (ton nombre d'élément est fini).

---

Évidemment que le nombre d'éléments est fini.
Mais imaginons que le nombre total de séquences différentes est 1000000, et que le langage ne permet de représenter que 800000 entiers (oui je sais, ces valeurs sont farfelues…).
Comment fait-on ?
On se débrouille avec les 800000 séquences disponibles ?
Mouais… ça peut marcher tant qu'on n'a pas besoin de plus de séquences…

Citation:

---

Envoyé par pseudocode

En procédant par dichotomie pour les tirages, tu peux te passer de la vérification. Il suffit de tirer un numero d'ordre dans un des intervalles

Par exemple, si on imagine 100 numeros d'odre possible:
>intervalles : [0,100[
tirage : 33

->intervalles : [0,33[ & ]33,100[
tirage : 54

->intervalles : [0,33[ & ]33,54[ & ]54,100[
...

---

Si tu connais un langage auquel on peut dire : « j'aimerais un nombre pseudo-aléatoire compris entre tant et tant, mais pas telle, telle, telle et telle valeurs. », je suis preneur…
À moins que l'on « choisisse » l'intervalle dans lequel tirer le nombre pseudo-aléatoire ?

Citation:

---

Envoyé par Steph_ng8

Comment fait-on ?
On se débrouille avec les 800000 séquences disponibles ?
Mouais… ça peut marcher tant qu'on n'a pas besoin de plus de séquences…

---

Effectivement, on peut se retrouver limiter par les types natifs du langage (int, long). Après il faut gérer soit meme des types plus grands.

Citation:

---

À moins que l'on « choisisse » l'intervalle dans lequel tirer le nombre pseudo-aléatoire ?

---

Oui, c'est la méthode la plus simple.

Ok.
Merci. :)

Je vais voir ce que ça donne.
Je te tiens au courant. ;)

Bon, alors j'ai fait un programme en C (pour l'instant).
Pour générer 150 000 séquences de 2 chiffres + 5 lettres, il faut :

• 80 secondes en faisant un tirage par caractère de chaque séquence
• à peine 30 secondes en tirant seulement le numéro d'ordre.

Pour des tailles d'exécutable équivalentes.

Ça divise presque par 3 la durée de génération. :ccool:
Par contre, pour l'instant je ne choisis pas l'intervalle dans lequel tirer les nombres pseudo-aléatoires.
Ce sera l'objet de la prochaine comparaison. ;)

Citation:

---

Envoyé par Steph_ng8

Ça divise presque par 3 la durée de génération. :ccool:
Par contre, pour l'instant je ne choisis pas l'intervalle dans lequel tirer les nombres pseudo-aléatoires.
Ce sera l'objet de la prochaine comparaison. ;)

---

Tu veux dire que tu fais une recherche pour savoir si le numero a déjà été tiré ?

Exact.
Je conserve une liste (enfin un tableau) des numéros déjà tirés, et je vérifie à chaque fois que le nouveau numéro n'est pas déjà présent.

Citation:

---

Envoyé par Steph_ng8

Exact.
Je conserve une liste (enfin un tableau) des numéros déjà tirés, et je vérifie à chaque fois que le nouveau numéro n'est pas déjà présent.

---

un algo de recherche optimisé pourrait peut être te faire gagner un peu de temps.

Si tu en connais un, je suis preneur.
Étant que le tableau n'est pas trié (et je ne vais pas m'amuser à le faire), je ne peux pas utiliser « bsearch ».

En C++, j'utiliserais « find ».
En Java, j'utiliserais « contains » avec un conteneur, ou une recherche simple avec un tableau.
En Python, j'utiliserais « in ».
En Perl… euh… je ne me suis pas encore assez documenté, mais il doit bien avoir une fonction qui le fait.
En PHP, j'utiliserais « in_array ».

Mais en C…

Bonjour,

en utilisant un générateur de nombres pseudo-aléatoires avec une période très grande, tu ne devrais même pas avoir besoin de tester si tu as tiré deux fois la même chose. Regarde du côté de Mersenne Twister par exemple.

Merci, je vais me renseigner.

Je crois que j'ai mieux…
J'ai fait des tests en C++ avec divers conteneurs, histoire de…

En utilisant std::vector, std:: deque ou std::list, j'obtiens des preformances moins bonnes qu'avec un tableau.
Par contre, avec std::set, le résultat est obtenu en moins d'une seconde (contre 30 secondes, je le rappelle) ! :mouarf: :mouarf: