Discussion :

[valentin03]

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.

[balkany]

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

[valentin03]

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

[valentin03]

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

[Flodelarab]

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é

[valentin03]

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

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.

[dourouc05]

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 .

[Flodelarab]

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)

[valentin03]

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

[Flodelarab]

Mais c'est la mêêêêêême.

[valentin03]

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.

[wiwaxia]

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:

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

[Guesset]

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