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

[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]

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é