Discussion :

[Steph_ng8]

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…

[pseudocode]

Bonjour,

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.

[Steph_ng8]

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.

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 » ?

[pseudocode]

Et comment on le « prend » ?

Au hasard. Par exemple par dichotomie.

[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.

Ç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.

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

[pseudocode]

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.

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)

Ç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[
...