Discussion :

[BoneBreaker]

Bonjour,

Voilà mon problème : j'ai besoin de mettre au point un système capable de générer des aléatoires (entiers) reproductibles. J'entends par là qu'ils sont générés à partir d'une chaîne et si on relance la fonction on retombe sur la même valeur.

Comme je n'ai besoin que d'aléatoires de petite taille (dans [0, 999] même souvent [0, 99]) J'ai essayé de me débrouiller avec une fonction crc32() dont je ne conservais que 2 ou 3 chiffres. Techniquement, ça marche très bien, en réinjectant la chaîne j'obtiens bien le même aléatoire, naturellement. Seulement je me suis aperçu que cette méthode ne couvrait pas toutes les valeurs de l'intervalle de résultats, il y a des trous. Par exemple si je la teste sur [1, 500], il va me couvrir au maximum 443 valeurs mais m'en laisser 57 de côté. Le hic c'est que j'ai impérativement besoin que tout l'intervalle soit couvert. Par ailleurs, je ne suis vraiment pas certain que la répartition soit équiprobable, à vue d'oeil et sur un nombre de résultats comparables, elle semble moins lisse que mt_rand().

Notons que la chaîne injectée est elle même un aléatoire mt_rand(1, 1000), lorsque je la modifie ou si j'essaye de lui simuler une sorte de fausse récursivité en lui injectant un premier résultat de mon aléatoire reproductible, ça n'a qu'une influence mineure sur le problème puisque l'intervalle n'est toujours pas parcouru intrégralement, seules les valeurs "absentes" changent. Bref, clairement le crc32 ne solutionnera pas mon problème.

Le projet est en PHP, j'aurais pu poster là-bas mais j'ai pensé que la solution serait en fin de compte plus mathématique/algorithmique que PHP donc je suis venu ici, n'hésitez pas à me déplacer si vraiment je suis hors-sujet. Merci.

[millie]

il va me couvrir au maximum 443 valeurs

Sur combien de génération ?

Car, probabilitairement parlant, il est impossible de vérifier que ta fonction renvoit des nombres de manière équiprobable.

Par exemple, sur [1 - 10].

La probabilité d'avoir 1 en un tirage est 1/10, de l'avoir n fois d'affilé est de :
(1/10)^n qui est non nul.


Donc ça ne m'étonne pas que tous les nombres ne soient pas couvert, puisque la probabilité au bout de n tirages qu'un nombre ne soit jamais sorti est non nul strictement.

J'entends par là qu'ils sont générés à partir d'une chaîne et si on relance la fonction on retombe sur la même valeur.

C'est que ce n'est pas aléatoire !!!

j'ai impérativement besoin que tout l'intervalle soit couvert

Si tu es sûr que tout l'intervalle soit couvert avec n tirages, c'est que le tirage n'est pas aléatoire.

[MasterOfChakhaL]

Salut,

Vu que tu veux couvrir un intervalle sans faire de trou, je pense que tu devrais orienter tes recherches vers des permutations (comme quand tu mélanges un jeu de cartes)

Pour la reproductibilité, tu pourrais établir des règles de permutations qui peuvent s'écrire sous une forme de chaine de caractères générée aléatoirement mais avec un format défini...

Par exemple, 1|21|5|32....
signifie, permuter les éléments 1 et 21, puis, permuter les éléments 5 et 32...

Il doit y avoir plus simple... mais c'est tout ce qui me vient a l'esprit...

[millie]

Si tu souhaites tirer des nombres entre 0-500 et qu'il n'y ait pas de doublons (par rapport aux nombres tirés avant).

Il y a le lien du forum suivant :
http://www.developpez.net/forums/sho...d.php?t=191130

[Nemerle]

Il faut préciser ton problème. Sur ton exemple [1,500] est-ce que tu veux:

1. Qu'au bout de 500 tirages les 500 valeurs soient toutes obtenues (shuffle random)
2. Que les probabilités soient toutes en 1/500 a priori ?

Je pourrais te répondre alors

[BoneBreaker]

Merci à tous pour vos réponses, je m'aperçois que j'avais très mal formulé mon affaire.

Millie : j'ai fait mes tests sur une boucle de 500 000 calculs, voilà par exemple les premiers résultats pour l'intervalle (0, 1000), entre crochets la valeur, après le => le nombre de fois qu'elle est tombée :

[1] => 990
[4] => 1553
[5] => 972
[6] => 517
[7] => 492
[8] => 485
[10] => 495
[11] => 1045
[12] => 1018
[13] => 1491
[14] => 928
[16] => 509
[20] => 982

On voit bien que c'est largement incomplet (manque 2, 3, 9 etc.) et à vue d'oeil pas du tout équiprobable, l'écart-type est considérable : il m'a trouvé 628 réulstats au lieu des 1000 escomptés donc la moyenne serait de 796, on en est loin rien que dans ces premiers résultats avec le 1553 notamment.

Sinon tu as raison je n'en avais pas conscience mais en effet il n'y a pas d'aléatoires dans mon affaire.

En essayant de le formuler proprement je me rends compte de l'aspect tordu de la chose : avec des manipulations simples je peux assez facilement "décaler" mon aléatoire "générateur" et le faire rentrer dans l'intervalle cible avec un modulo, à condition qu'il soit lui-même déjà un entier (c'est le cas dans la plupart de mes utilisations, mais pas nécessairement toutes).

En fait si je devais reformuler je dirais plutôt : comment passer d'une chaîne alphanumérique aléatoire (décrivant par exemple [a-zA-Z0-9]{n}) à un entier dans un intervalle intégralement décrit et ce de façon équiprobable. Une sorte de projection d'un espace vectoriel sur un de ses sous-espaces, si je puis dire... mais bon je m'égare, en tout cas ça a l'air encore plus épineux vu comme ça.

Ce que j'essayais de faire revenait vaguement à ça, via crc32(). Mais voilà cette fonction n'a absolument aucune raison d'être équiprobable en ce qui concerne la position de chaque chiffre dans la chaîne retournée, puisque c'était ce que j'utilisais. D'où les trous et la distribution erratique.

Désolé de vous avoir fait perdre votre temps avec la première version mal formulée, j'espère que maintenant c'est plus clair.

[Jean-Marc.Bourguet]

En fait si je devais reformuler je dirais plutôt : comment passer d'une chaîne alphanumérique aléatoire (décrivant par exemple [a-zA-Z0-9]{n}) à un entier dans un intervalle intégralement décrit et ce de façon équiprobable. Une sorte de projection d'un espace vectoriel sur un de ses sous-espaces, si je puis dire... mais bon je m'égare, en tout cas ça a l'air encore plus épineux vu comme ça.

Est-ce que considérer tes chaînes comme des nombres écrits dans une base (26+26+10=62) ne résoudrait pas ton problème.

[Nemerle]

Sinon tu as raison je n'en avais pas conscience mais en effet il n'y a pas d'aléatoires dans mon affaire.

Dans ce cas, utilise une algo de génération de nombres pseudo-aléatoires par permutations: algorithme de Fisher-Yates (go google!)

Autrement, mais je ne suis plus sur, le Mersenne Twister est équidistribué et se génère à partir d'une vecteur de départ, un seed. Je crois que si tu rejoues le vecteur de départ ca te redonne la même série (à vérifier)

[BoneBreaker]

Autrement, mais je ne suis plus sur, le Mersenne Twister est équidistribué et se génère à partir d'une vecteur de départ, un seed. Je crois que si tu rejoues le vecteur de départ ca te redonne la même série (à vérifier)

Merci pour Fisher-Yates, sinon oui tu as raison pour mt_srand() mais il est sujet à "l'overseed" comme on dit : j'ai essayé de mettre mon vrai aléatoire en seed et là il délire totalement en me donnant seulement 20 résultats différents au lieu des 1000 attendus. Apparemment le seed n'est pas sensé être appelé plus d'une fois pas script et comme j'ai des boucles ça ne marchera pas.

[BoneBreaker]

Est-ce que considérer tes chaînes comme des nombres écrits dans une base (26+26+10=62) ne résoudrait pas ton problème.

C'est une très bonne idée en effet, merci. Je ne suis pas trop habitué à ce genre de gymnastique mais c'est certainement une direction à explorer.

[Nemerle]

Merci pour Fisher-Yates, sinon oui tu as raison pour mt_srand() mais il est sujet à "l'overseed" comme on dit : j'ai essayé de mettre mon vrai aléatoire en seed et là il délire totalement en me donnant seulement 20 résultats différents au lieu des 1000 attendus. Apparemment le seed n'est pas sensé être appelé plus d'une fois pas script et comme j'ai des boucles ça ne marchera pas.

attention, une nouvelle version du MT est disponible, va voir sur le site du MIT

Par ailleurs, pourquoi réinitialiser ton seed dans tes boucles? Une fois fixé, cela devrait etre bon, non?

[BoneBreaker]

Par ailleurs, pourquoi réinitialiser ton seed dans tes boucles? Une fois fixé, cela devrait etre bon, non?

Oui exact je l'utilisais mal, en effet il permettrait de retrouver la série complète. Ca m'obligerait en plus à stocker la position du tirage dans la série. Un peu lourd par rapport à la façon dont mes objets sont définis mais si je ne trouve pas d'autre moyen je vais considérer l'idée, merci.

[davcha]

Voilà mon problème : j'ai besoin de mettre au point un système capable de générer des aléatoires (entiers) reproductibles. J'entends par là qu'ils sont générés à partir d'une chaîne et si on relance la fonction on retombe sur la même valeur.

Tu cherches à faire une fonction de hachage en gros, non ?

[Graffito]

Bonjour,

Une solution simple consisterait à créer au préalable la liste des nombres pseudo aléatoires. On gerera pour celà un tableau d'élements qui contiendront :
- la chaine de caractère,
- son CRC,
- sa position initiale,
- le nombre pseudo aleatoire (non initialisé au départ)

La procedure consisterait à :

• remplir le tableau avec le CRC associé à la chaine et le n° d'ordre de la chaine
• trier le tableau suivant les CRC obtenus et la position initiale
• affecter au nombre pseudo-aléatoire la position (dans le tableau trié) modulo 1000 pour obtenir une valeur de 0 à 999.
• retrier suivant la position initiale

.

[BoneBreaker]

Merci à tous pour vos réponses, en attendant d'avoir le temps de me pencher plus longuement sur le sujet j'ai réussi à contourner le problème dans le cas le plus critique.