Forum Programmation.autre Générer un nombre pseudo aléatoire avec garantie d'unicité

Posté par  .
Étiquettes : aucune
1
13
fév.
2012

Bonjour,

Je suis à la recherche de l'algorithme miracle qui me permettrais d'obtenir un nombre pseudo aléatoire en étant sûr de ne jamais tomber 2 fois sur la même valeur.

Dans l'idéal je cherche a obtenir une fonction f qui pour tout x appartenant à [0..n] associe un nombre y appartenant à [0..n]. Avec pour tout x != y: f(x) != f(y)

Dans mes recherches je suis tombé sur les Champs de Galois, mais quelques tests (maladroits, je n'ai pas tout compris) m'ont donné l'impression que la sortie n'était pas forcément unique.

Ce n'est en aucun cas pour des besoins cryptographiques ou de sécurité, donc le caractère aléatoire n'a pas besoin d'être absolu, il doit juste "sembler" aléatoire.

Avez-vous des lectures sur le sujet ?
Merci pour vos lumières.

  • # Question bizarre

    Posté par  . Évalué à 5.

    Euh, j'ai pas bien compris ton besoin...
    Au vu de la formulation de ta fonction

    pour tout x != y: f(x) != f(y)

    je te dirais bien de prendre la fonction f(x)=x, mais bon, ça n'est plus vraiment aléatoire.

    Remarque, que si tu prends une fonction aléatoire, je ne vois plus comment tu peux garantir que cette fonction soit injective.

    Sinon, si tu cherches un vrai générateur de nombres aléatoires, demande à une classe de collégiens de faire des multiplications : le résultat devrait de convenir (et tu pourrais peut-être même avoir l'injection)

  • # une idée pour une liste pas trop importante

    Posté par  . Évalué à 1.

    Si la liste [0..n] n'est pas trop grande on peut créer la liste image par f assez simplement.

    creer une liste L1 <-- [O..n]
    creer une liste vide Lf <-- []

    tant que L1 non vide faire
    N=random(taille de L1)
    ajouter l'élément numéro N de L1 à la fin de la liste Lf
    supprimer élément numéro N de L1
    fin boucle

    et on devrait avoir une liste Lf avec tous les élément de [0..n] classé à peu près aléatoirement.

    • [^] # Re: une idée pour une liste pas trop importante

      Posté par  . Évalué à 0.

      J'ai songé à faire quelque chose de ce genre mais j'ai n assez grand (environ 33,5 millions (2^25)), et de plus je souhaiterais plus tard refaire la même chose avec n encore plus grand (2^100).

      En fait je souhaite qu'à chaque appel de ma fonction, un nombre différent des précédents ET qui semble aléatoire soit retourné (i.e. que lorsqu'on a déjà vu les derniers chiffres, le nouveau ne semble pas évident).

      Ce nombre retourné va par la suite être stocké dans une BDD, idéalement l'index de la BDD sera x et le nombre sera f(x).
      J'ai d'abord songé faire un bête RANDOM dans une boucle qui vérifie si il n'existe pas déjà dans la BDD mais une fois 33 millions de lignes entrées, cette boucle risque de tourner longtemps avant de retourner un chiffre valide.

      D'où l'idée d'une telle fonction.

      • [^] # Re: une idée pour une liste pas trop importante

        Posté par  (site web personnel) . Évalué à 1.

        L'idée n'est pas de prendre un nombre aléatoire et voir si il a déjà été tiré mais d'avoir une liste de nombres disponibles et de tirer aléatoirement l'index du prochain nombre.

        Le pb c'est de pouvoir stoker 2^100 nombres. Mais si tu veux les stocker après, ça te posera peut être pas de problème de les stocker avant.

        Matthieu Gautier|irc:starmad

      • [^] # Re: une idée pour une liste pas trop importante

        Posté par  . Évalué à 2. Dernière modification le 13 février 2012 à 22:52.

        2^100

        1/ J’espère que tu réalises que c’est impossible à faire avec une machine même 64 bits qui ne peu décrire que 2⁶⁴ nombres différents, à moins d’utiliser un outil à précision arbitraire.

        2/ Je me demande le temps que ça va prendre…

        Du coup me vient une idée, je ne sais pas à quel point tu veux que ce soit aléatoire, mais tu peux peut-être t’arranger pour tirer dans un sous-ensemble différent à chaque fois. Par exemple tu tires dans [0, 100[, puis dans [1, 101[, etc. Tu sais que ton 100ème tirage sera disjoint de ton premier, du coup tu peux stocker la liste des 100 derniers nombres tirés, plus l’intervalle de tirage, et ensuite utiliser un algo. pseudo-aléatoire classique (mais faudra prendre quelque chose de très rapide…).

        EDIT : c’est l’idée de Kerro en-dessous, désolé pour le bruit.

        • [^] # Re: une idée pour une liste pas trop importante

          Posté par  . Évalué à 1.

          Pour ton 1/ je ne connais pas assez bien les autres langages, mais le type long de python est capable de bien plus que 2^100 (il n'est apparemment limité que par la quantité de mémoire virtuelle).

          2/ D'où l'idée de ne pas tout générer et chercher une fonction qui me retourne un tel nombre aléatoire. Chose que je viens de trouver dans des commentaires plus bas.

  • # Si tu trouve

    Posté par  . Évalué à -1.

    tu deviendra célébre.
    D'habitue on as un morceau de hardware pour faire ca (voir extraire le bruit thermique d'une résistance http://fr.wikipedia.org/wiki/Bruit_thermique ).

    Sinon la fonction random de la libc utiliser des tables de "hasard" pré-définie qu'il convient d'initialiser avec une valeur de timer système pour sélectionner l'emplacement de départ de parcours de la table.
    voir
    int rand(void);
    void srand(unsigned seed);

    Si tu veut faire une table toute prete toi meme en voici, tu peut mélangé tout ca pour en faire des customs

    http://nte-serveur.univ-lyon1.fr/nte/immediato/math2001/tables/TABLAZAR.htm
    http://www.mines.inpl-nancy.fr/~verdel/stat/tables/mod.php?id=t1.php

    Le pseudo hasard pour l'utiliser tu peut croiser plusieurs informations temporelle (asynchrone) comme le temps de démarrage de ton programme, le temps système en milli-seconde et des tables (pointeur sur ton code par exemple) et une table et ton résultat est difficilement reproductible.
    Par améliorer l'entropie du hasard le kernel linux utiliser les interruptions du matériel qui sont identifié pour être non-cyclique (comme le temps entre deux clics souris et les frappes au claviers).

    • [^] # Re: Si tu trouve

      Posté par  . Évalué à 1.

      Comme précisé dans mon message, je ne souhaite pas faire du hasard parfait, je souhaite juste avoir une impression de hasard, et même pire que ça, je souhaite avoir un "hasard" que je peux prévoir. Ma seule contrainte est qu'il n'y ai pas 2 nombres égaux.

  • # Exemple d'algo

    Posté par  . Évalué à 3.

    Tu génères ton nombre en deux parties:
    1. une partie qui s'incrémente à chaque fois (ou +42 à chaque fois, comme tu veux. Ou même un incrément aléatoire strictement positif)
    2. une partie aléatoire
    3. pour les besoins cosmétiques, tu permutes les décimales ou les bits (toujours de la même manière)

    Tant que ton incrément ne boucle pas, tu as la garantie absolue de ne jamais avoir deux fois le même nombre.

    Sinon en plus court, tu prends juste le 1 (et le 3 pour la cosmétique).

    • [^] # Re: Exemple d'algo

      Posté par  . Évalué à 0.

      Merci, c'est une piste intéressante.

      Je vais creuser ça pour obtenir ma dernière condition : Je souhaite que la sortie soit aussi dans [0..n].

    • [^] # Re: Exemple d'algo

      Posté par  . Évalué à 1.

      En le générant ainsi, vos nombres auront peut-être une mauvaise distribution aléatoire. Il faudrait tester avec un outil comme ent.

      • [^] # Re: Exemple d'algo

        Posté par  . Évalué à -1.

        Ça n'est pas important pour mon cas d'utilisation, le caractère aléatoire doit seulement être ressenti.

  • # Ordre de grandeur de n ?

    Posté par  . Évalué à 2.

    Si n est grand, tu peux orienter tes recherches vers les fonctions de hachage et le paradoxe des anniversaires, ou bien carrément prendre la sortie d'un chiffrement de flot, avec une clef que tu maintiens secrète, et prendre ton nombre en entrée pour IV (juste pour avoir un peu d'aléa hein, mais surtout pas pour faire de la sécurité ni utiliser cet aléa à des fins cryptographiques).

    Sinon tu veux sans doutes parler des corps de Galois (plutôt que champs, mauvaise traduction de "field" en mathématiques !), c'est-à-dire de corps finis.

  • # Registre à décalage

    Posté par  . Évalué à 2.

    En électronique, pour faire un générateur pseudo-aléatoire, on utilise un registre à décalage. Si tu as un registre de n bits, alors tu balayes les 2^n - 1 (pas le zéro) valeurs possibles d'une façon qui semble aléatoire. Une fois que tu as passé toutes les valeurs possibles, alors tu repars sur la même séquence. Tu as donc du pseudo-aléatoire reproductible, et si n est suffisamment grand, tu n'auras jamais deux fois la même valeur. Ça se simule avec un simple polynôme en base 2 (par contre il doit répondre à certains critères, on ne peut pas prendre n'importe quel polynôme).
    http://fr.wikipedia.org/wiki/Registre_%C3%A0_d%C3%A9calage#Registre_.C3.A0_d.C3.A9calage_avec_r.C3.A9troaction_lin.C3.A9aire

  • # Permutation

    Posté par  (site web personnel) . Évalué à 2.

    J'ai l'impression que tu cherches à simuler une permutation aléatoire.
    De nombreux algorithmes existent pour ça.
    Un bon point d'entrée:
    http://fr.wikipedia.org/wiki/Permutation_al%C3%A9atoire

    • [^] # Re: Permutation

      Posté par  (site web personnel) . Évalué à 2.

      Le problème de cette approche c'est que ça ne scale pas fort bien puisqu'il faut « trier » tous tes nombres dès le départ (au mieux O(n)).

      pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

      • [^] # Re: Permutation

        Posté par  (site web personnel) . Évalué à 2. Dernière modification le 14 février 2012 à 10:00.

        (au mieux O(n))

        Je suis capable de trier n + 1 nombres distincts compris entre 0 et n + 1 en O(1), moi! :)

        D'ailleurs je ne vois pas le O(n), les algorithmes de tri c'est soi O(n ln n) pour les tris avec comparaison, soit O(1) si tu utilises une H-fonction, si je me souviens bien!

        • [^] # Re: Permutation

          Posté par  . Évalué à 2.

          en:Dutch_national_flag_problem

          Je suis capable de trier n + 1 nombres distincts compris entre 0 et n + 1 en O(1), moi! :)

          En O(n), je vois, mais en O(1), je voudrais bien voir votre algorithme.

          • [^] # Re: Permutation

            Posté par  (site web personnel) . Évalué à 2.

            Argh je me suis trompé, c'est n+1 nombres distincts entre 0 et n que je sais faire vite!

            • [^] # Re: Permutation

              Posté par  . Évalué à 2.

              Je suis preneur quand même.

              • [^] # Re: Permutation

                Posté par  (site web personnel) . Évalué à 2. Dernière modification le 14 février 2012 à 17:05.

                Ben il n'y a rien à faire la réponse c'est: 0, 1, …, n.

                • [^] # Re: Permutation

                  Posté par  . Évalué à 3. Dernière modification le 14 février 2012 à 19:17.

                  Et bien il faut la générer quand même cette liste, et c'est en O(n), à moins que vous ne preniez comme hypothèse de départ que la liste existe et qu'elle est déjà triée, mais avec ce genre d'hypothèses on peut résoudre un certains nombre de problèmes facilement en O(1).

                  • [^] # Re: Permutation

                    Posté par  (site web personnel) . Évalué à 2.

                    Et bien il faut la générer quand même cette liste, et c'est en O(n)

                    Ah oui tiens… :)

                    à moins que vous ne preniez comme hypothèse de départ que la liste existe et qu'elle est déjà triée,

                    loin de moi ce genre d'idée!

        • [^] # Re: Permutation

          Posté par  (site web personnel) . Évalué à 3.

          J'ai mis « trier » entre guillemets parce que ça n'est pas un tri. L'algo O(n) et sur la page citée plus haut : http://fr.wikipedia.org/wiki/Permutation_aléatoire#Algorithme_de_Fisher-Yates

          Si tu arrives à générer une permutation aléatoire (telle que toutes les permutations possibles soient équiprobables) en moins que O(n) en temps ou en mémoire je suis intéressé.

          pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

          • [^] # Re: Permutation

            Posté par  (site web personnel) . Évalué à 3.

            Si tu arrives à générer une permutation aléatoire (telle que toutes les permutations possibles soient équiprobables) en moins que O(n) en temps ou en mémoire je suis intéressé.

            Ce n'est pas possible parceque si j'ai une algo permutant aléatoirement un tableau T de taille n avec complexité meilleure que O(n) alors il y a toujours au moins une valeur non permutée tandis qu'il existe des permutations sans point fixe: l'algo n'est pas équiprobable.

            Le mélange de Knuth/Fisher-Yates, que tu viens de me faire découvrir, est très beau parceque la preuve d'équiprobabilité est d'une simplicité merveilleuse.

          • [^] # Re: Permutation

            Posté par  . Évalué à 2.

            Merci, c'est intéressant. De cet algorithme, je ne connaissais que l'utilisation "prendre un élément aléatoire dans une liste dont on ne connait pas la taille à l'avance et sans tout stocker".

  • # générateur congruentiel linéaire ?

    Posté par  (site web personnel) . Évalué à 8.

    La manière type de construire un PRNG est d'utiliser un générateur congruentiel linéaire et ça te garanti de n'avoir aucune répétition sur la durée du cycle. Il suffit donc de s'arranger pour avoir un générateur qui fait des périodes pleines égales à n.

    http://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length

    pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

    • [^] # Re: générateur congruentiel linéaire ?

      Posté par  . Évalué à 3. Dernière modification le 14 février 2012 à 10:05.

      Merci, je crois que tu viens de pointer exactement ce qu'il me faut. Je viens de faire un exemple avec un générateur de nombre aléatoires entre 0 et 99 répondant à mes critères.
      Le code (crade) en python pour ceux que ça pourrait intéresser:

      def X(Xn):
    a = 21
    c = 33
    m = 100

    return (a*Xn+c) % m

X0 = 52 # Seed
Xi = X0
for i in xrange(0,100):
    print str(i)+", "+str(Xi)    
    Xi = X(Xi)

      Les valeurs choisies:
      m : correspond à ma plage [0..99]
      c : est premier avec m (j'aurais pu choisir n'importe lequel de 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97 ou 99)
      a : est défini tel que a-1 est divisible par tout les facteurs premiers de m (m = 2^2+5^2 en l’occurrence) ainsi que si m multiple de 4 (ce qui est le cas ici), alors a est aussi multiple de 4. Je n'ai donc pas le choix ici, a-1 = 2*2*4 = 20 => a = 21

      La graine (X0, Seed) peut être n'importe quel nombre entre 0 et 99.

      Merci beaucoup, mon seul problème est maintenant de trouver un "a" et un "c" correspondant à mon "m" énorme de 2^25...

      • [^] # Re: générateur congruentiel linéaire ?

        Posté par  (site web personnel) . Évalué à 3.

        Merci beaucoup, mon seul problème est maintenant de trouver un "a" et un "c" correspondant à mon "m" énorme de 2^25...

        Apparemment tes maths sont un peu loin. :)

        Trouver des nombres c premiers à 2^25 n'est pas sorcier, il suffit de prendre n'importe quel nombre qui n'est pas divisible par 2.

        Tu es dans un cas où m est manifestement multiple 4 et où son seul facteur premier est 2. Donc pour a = 4k + 1 avec k de ton choix, tu obtiens un nombre répondant aux critères que tu énonces.

  • # Compléments

    Posté par  (site web personnel) . Évalué à 2.

    Je voudrais compléter la réponse de Krunch, à laquelle je souscris tout à fait.

    Ce n'est en aucun cas pour des besoins cryptographiques ou de sécurité, donc le caractère aléatoire n'a pas besoin d'être absolu, il doit juste "sembler" aléatoire.

    On ne sait rien faire d'autre que des choses qui semblent aléatoire, c'est pour ça qu'on parle de générateur de nombres pseudo-aléatoires, comme tu le fais aussi.

    Pas facile d'expliquer ce qu'est le hasard! D'ailleurs l'idée même qu'une suite de nombres aléatoires ait certaines propriétés est un peu contradictoire, que peut-on légitimement attendre du hasard? Au contraire les suites de nombres pseudo-aléatoires ont plein de propriétés! (Quelques propriétés importantes des suites suivant une loi uniforme.)

    Si tu retournes à ton problème, je suis sûr que tu seras d'accord que c'est ce qui t'empêche le plus de trouver une solution toi-même: tu ne sais pas assez ce que tu veux dire par «avoir l'air aléatoire.»

    Dans mes recherches je suis tombé sur les Champs de Galois …

    La traduction française de Galois field est corps fini ou à la rigueur corps de Galois mais le premier est beaucoup plus fréquent.

    Un corps K est un ensemble dont tu sais ajouter et multiplier et diviser les éléments, comme s'il s'agissait de nombres ordinaires (par exemple les nombres rationnels Q ou les nombres réels R). Dans un corps fini, l'ensemble des éléments non-nuls est obtenu en calculant les puissances d'un élément dit primitif (pour chaque corps — sauf F2 :) — plusieurs choix sont possibles). Comme il y a d'autres méthodes (plus faciles!) pour énumérer cet ensemble, cela fournit une méthode pour faire des mélanges.

    Merci pour vos lumières.

    Lunettes de soleil non fournies. Pardon pour cette vanne pourrie. J'ai honte de moi.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.