IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Aléatoire contraint aux poids


Sujet :

Algorithmes et structures de données

  1. #1
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut Aléatoire contraint aux poids
    Bonjour, comment vous vous y prendriez ?
    Le but: Attribuer des poids à des strings dans un tableau (le poids est dans la string au mot m), et
    les tirer aléatoirement en fonction des poids. (je n'ose pas demander du pseudo code, qui serait pourtant le bienvenu).
    Je bueugue total, des explications seraient aussi les bienvenues.
    Merci aux savants.
    Savoir pour comprendre et vice versa.

  2. #2
    Membre éprouvé Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    315
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 315
    Points : 907
    Points
    907
    Par défaut
    C'est vague… il y a mille manières d'attribuer des poids à des chaines de caractères, et mille manières de faire ensuite un tirage aléatoire.
    Peux-tu préciser un peu le contexte, et / ou ce que tu entends par « le poids est dans la string au mot m » et « les tirer aléatoirement en fonction des poids » ?

  3. #3
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par balkany Voir le message
    C'est vague… il y a mille manières d'attribuer des poids à des chaines de caractères, et mille manières de faire ensuite un tirage aléatoire.
    Peux-tu préciser un peu le contexte, et / ou ce que tu entends par « le poids est dans la string au mot m » et « les tirer aléatoirement en fonction des poids » ?
    Cite: « le poids est dans la string au mot m ?
    Le poids c'est un "x" entre 1 et 10 contenu dans la string. (pas de soucis pour l'extraction).
    Cite: « les tirer aléatoirement en fonction des poids ?
    Que ceux de moins que 5 sortent "k*x" fois moins souvent et ceux de plus que 5, "k*x" fois plus.
    Comment maîtriser l'insaisissable aléatoire ?
    Mais est-ce encore de l'aléatoire...
    Savoir pour comprendre et vice versa.

  4. #4
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par valentin03 Voir le message
    Cite: « le poids est dans la string au mot m ?
    Le poids c'est un "x" entre 1 et 10 contenu dans la string. (pas de soucis pour l'extraction).
    Cite: « les tirer aléatoirement en fonction des poids ?
    Que ceux de moins que 5 sortent "k*x" fois moins souvent et ceux de plus que 5, "k*x" fois plus.
    Comment maîtriser l'insaisissable aléatoire ?
    Mais est-ce encore de l'aléatoire...
    En clair: Quel traitement faire subir au nombre qui sort du générateur aléatoire
    pour le soumettre sa fréquence à: x*k
    Savoir pour comprendre et vice versa.

  5. #5
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 771
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 771
    Points : 11 991
    Points
    11 991
    Par défaut
    Bonjour

    Les poids sont-ils des nombres entiers naturels ? Si oui, il suffit répéter le mot un nombre de fois égal au poids, et tirer de façon equiprobable un mot.

    Exemple:

    Maman 6
    va 2
    au 1
    marché 5
    Cette liste devient :

    Maman
    Maman
    Maman
    Maman
    Maman
    Maman
    va
    va
    au
    marché
    marché
    marché
    marché
    marché
    
    On tire un nombre entre 1 et 14 : 11
    Le mot à la onzième place est "marché".

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    $ cat <<eof >fichier.txt
    > Maman 6
    > va 2
    > au 1
    > marché 5
    > eof
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt
    Maman
    Maman
    Maman
    Maman
    Maman
    Maman
    va
    va
    au
    marché
    marché
    marché
    marché
    marché
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    Maman
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    marché
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    au
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    marché
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    va
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    marché
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  6. #6
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par valentin03 Voir le message
    En clair: Quel traitement faire subir au nombre qui sort du générateur aléatoire
    pour soumettre sa fréquence à: x*coeff k
    J'ai bien une méthode bourrin:
    Compter les "ns" sorties
    Stocker "n" aléatoire sorti et son "ns"
    Et pour chaque sortie, aller voir depuis combien de temps il n'est pas sorti.
    Il y a peut-être mieux ...?

    Citation Envoyé par Flodelarab Voir le message
    Les poids sont-ils des nombres entiers naturels ? Si oui, il suffit répéter le mot un nombre de fois égal au poids, et tirer de façon equiprobable un mot.
    Houla, l'imparable de la simplicité a frappé.
    Quand y a pas d'algo, y a pas de problème d'algo.
    Mais quand même c'est plus joli avec un algo.
    Savoir pour comprendre et vice versa.

  7. #7
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    26 060
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 26 060
    Points : 185 691
    Points
    185 691
    Par défaut


    Une autre solution, inspirée des probabilités discrètes de manière très directe. On suppose que tous les poids se somment à un (dans le cas contraire, il suffit de normaliser : diviser chaque poids par la somme des poids). Ensuite, on détermine la CDF (fonction de répartition, en français). Finalement, on tire un nombre de manière aléatoire entre 0 et 1 (bornes incluses) et on inverse la CDF : à quel mot correspond cette valeur de la CDF ?

    De manière plus détaillée, sur un exemple (ça marche mieux ). On considère avoir trois mots : a (poids 4), b (poids 3,5) et c (poids 2).
    Normalisation des poids : la somme vaut 4 + 3,5 + 2 = 9,5. Donc on a : a 0,421, b 0,368, c 0,211. Ces trois poids se somment bien à 1. On a déterminé la densité de probabilité (même si ce mot est plutôt réservé aux distributions continues… Passons.)
    On détermine la CDF : entre 0 et 0,421, c'est a ; entre 0,421 et 0,421 + 0,368 = 0,789, c'est b ; entre 0,789 et 1, c'est c.

    Ensuite, on tire des nombres au hasard : 0,1 (on génère a : 0 <= 0,1 < 0,421) ; 0,5 (on génère b : 0,421 <= 0,5 < 0,789), 0,9 (on génère c : 0,789 <= 0,9 <= 1). Dans grosso modo tous les langages, tu as une fonction pour générer un tel nombre assez facilement.

    Sinon, les méthodes précédentes peuvent se généraliser aux cas où les poids ne sont pas entiers : il faut juste les multiplier par un même nombre jusqu'à ce que tous soient entiers. Dans mon exemple, il suffit de multiplier par 2 (a 8, b 7, c 4). Ça reste bourrin, 'faut pas se cacher .
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  8. #8
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 771
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 771
    Points : 11 991
    Points
    11 991
    Par défaut
    Tiens, puisqu'on en est à reformuler, voici une autre façon de le dire :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    total=somme(poids)
    score=nombre_aléatoire_entre(0,total)
    indice_mot=0
    TANT QUE score > 0
        score -= poids[indice_mot]
        indice_mot++
    FINTANTQUE
    afficher mot[indice_mot]
    (Dans ce genre de tirage aléatoire, 0 est toujours inclus et le total toujours exclu)
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  9. #9
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par dourouc05 Voir le message
    Une autre solution, inspirée des probabilités discrètes de manière très directe. On suppose que tous les poids se somment à un (dans le cas contraire, il suffit de normaliser : diviser chaque poids par la somme des poids). Ensuite, on détermine la CDF (fonction de répartition, en français). Finalement, on tire un nombre de manière aléatoire entre 0 et 1 (bornes incluses) et on inverse la CDF : à quel mot correspond cette valeur de la CDF ?
    ça c'est pas mal, c'est plus subtil que bourrin; je vais étudier ça, qui paraît plus rapide que ma méthode bourrin (#6), ou celle de Floredelarab
    Savoir pour comprendre et vice versa.

  10. #10
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 771
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 771
    Points : 11 991
    Points
    11 991
    Par défaut
    Mais c'est la mêêêêêême.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  11. #11
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    Mais c'est la mêêêêêême.
    C'est concis mais c'est trop ésotérique pour moi, puisque dans ton: "score=nombre_aléatoire_entre(0,total)" je voyais un comptage des sorties de: "nombre_aléatoire".
    Syntaxe = Tour de Babel de la programmation.

    Merci dourouc05, même en cent ans je n'aurais pu trouver un truc pareil.
    Savoir pour comprendre et vice versa.

  12. #12
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 184
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 75
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 184
    Points : 2 291
    Points
    2 291
    Billets dans le blog
    9
    Par défaut Maman va au marché
    Bonjour,

    J'ai repris l'idée de dourouc05 sans procéder à la normalisation des poids.
    Il suffit pour cela de disposer de la liste des sommes partielles commençant à zéro, et se terminant par la différence entre le total et le dernier coefficient.

    Le coeur du programme se réduit à peu d'instructions:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
               n:= Random(Total); k:= N_Mot;
               WHILE (n<Ls[k]) DO Dec(k);
    Voici l'affichage obtenu:

    Nom : Résultats.png
Affichages : 97
Taille : 9,0 Ko

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
      PROGRAM XXXX;
    
     USES Crt, E_Texte;
    
     CONST N_Mot = 4; Nm1 = N_mot - 1;
    
     TYPE Tab_Str = ARRAY[0..N_Mot - 1] OF String[7];
          Tab_E   = ARRAY[0..N_Mot - 1] OF Word;
    
     CONST ListeM: Tab_Str = (' Maman', ' va', ' au', ' marché');
           ListeE: Tab_E   = (4, 3, 2, 1);
    
     VAR Total: Word; ListeS: Tab_E;
    
     PROCEDURE Enumeration(Ls: Tab_E);
       VAR j, k, x, y: Byte; n, Smax: Word; Touche: Char;
       BEGIN
         RandSeed:= 1666555999; y:= 7;
         REPEAT
           Touche:= ReadKey; Inc(y);
           FOR j:= 1 TO 6 DO
             BEGIN
               x:= 13 * j;        Dec(x,10); GotoXY(x, y);
               n:= Random(Total); k:= N_Mot;
               WHILE (n<Ls[k]) DO Dec(k);
               E(0010); Write(n:2);
               E(0012); Write(k:3);
               E(0015); Write(ListeM[k])
             END
         UNTIL (Touche=#27)
       END;
    
     PROCEDURE Init_S(VAR L_: Tab_E; VAR T_: Word);
      CONST C1 = 3; L1 = 4; o = 9;
       VAR k, s: Word;
       BEGIN
         E(1011); Wt(C1, L1 - 1, 'Valeurs des coefficients:       ');
         E(0012); FOR k:= 0 TO Nm1 DO Write(ListeE[k]:9);
         E(0011); Wt(C1, L1 + 1, 'Valeurs des sommes successives: ');
         E(0014); s:= 0; L_[0]:= s; Write(ListeS[0]:o);
         FOR k:= 1 TO Nm1 DO BEGIN
                               Inc(s, ListeE[k - 1]); L_[k]:= s;
                               Write(ListeS[k]:o)
                             END;
         Inc(s, ListeE[k]); T_:= s;
         E(0010);           Write(Total:o)
       END;
    
     BEGIN
       Init_S(ListeS, Total); Enumeration(ListeS)
     END.
    @Flodelarab Sans vouloir en contester le contenu, je trouve ton pseudo-code un peu raide pour le lecteur débutant
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    TANT QUE score > 0
        score -= poids[indice_mot]
        indice_mot++
    FINTANTQUE


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #13
    Membre expérimenté

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    482
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 482
    Points : 1 520
    Points
    1 520
    Par défaut Dicho
    Bonjour,

    La réponse de Flodelarab est assez sympathique même si la concision la rend un peu plus difficile à lire.

    Si on recherche la performance, on peut :

    1. ajouter un champs sum qui cumule les poids (-1 pour le premier ) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     i  libellé poids sum
     0  Maman     6    5
     1  va        2    7
     2  au        1    8
     3  marché    5   13
    2. Ensuite tirer une valeur n entre 0 et sum_max ici 13 (inclus).

    3. Faire une recherche dichotomique de n (par exemple) dans sum :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    si n = 10.
    4/2 = 2 -> i  => "au"  sum = 8 < n = 10
    4/4  + i = 3 => "marché"  sum = 13 > n = 10 et sum -poids < n // That's all folks !
    On peut même faire l'économie du champ sum en le calculant dans poids si ce dernier n'est plus utilisé.

    Bien sûr pour 4 éléments, le jeu n'en vaut pas la chandelle mais pour des nombres plus conséquents...

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

Discussions similaires

  1. [2.x] Ajouter une contrainte aux éléments d'une collection
    Par Gaylord.P dans le forum Symfony
    Réponses: 5
    Dernier message: 11/12/2015, 17h36
  2. Accéder aux poids d'un réseau de neurones
    Par stockes dans le forum Méthodes prédictives
    Réponses: 0
    Dernier message: 22/10/2013, 10h50
  3. Réponses: 4
    Dernier message: 18/04/2007, 10h22
  4. Numeroter les tables par rapport aux contraintes
    Par nicassy dans le forum Outils
    Réponses: 10
    Dernier message: 02/02/2007, 11h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo