Aléatoire contraint aux poids

Version imprimable

21/06/2020, 15h47
valentin03

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.
21/06/2020, 16h26
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 » ?
21/06/2020, 16h49
valentin03

Citation:

Envoyé par 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 » ?

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...
21/06/2020, 16h59
valentin03

Citation:

Envoyé par 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

Bonjour :coucou:

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:

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é

21/06/2020, 17h09
valentin03

Citation:

Envoyé par 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 ...?

Citation:

Envoyé par Flodelarab

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.
21/06/2020, 23h12
dourouc05

:salut:

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 :mrgreen:). 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 :aie:.
22/06/2020, 10h06
Flodelarab
Tiens, puisqu'on en est à reformuler, voici une autre façon de le dire :
Code:

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)
22/06/2020, 18h59
valentin03

Citation:

Envoyé par 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 ?

ç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
23/06/2020, 01h02
Flodelarab

Mais c'est la mêêêêêême. :(
23/06/2020, 01h33
valentin03

Citation:

Envoyé par Flodelarab

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.

1 pièce(s) jointe(s)

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:

1
2
           n:= Random(Total); k:= N_Mot;
           WHILE (n<Ls[k]) DO Dec(k);

Voici l'affichage obtenu:

Pièce jointe 573845

Code:

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 :aie: pour le lecteur débutant

Code:

1
2
3
4
TANT QUE score > 0
    score -= poids[indice_mot]
    indice_mot++
FINTANTQUE

26/06/2020, 19h19
Guesset

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:

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:

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