Générer Une Pondéré Nombre Aléatoire
Je suis en train de concevoir une (bonne) manière de choisir un nombre aléatoire à partir d'une plage de numéros possibles où chaque nombre dans la plage a un poids. Pour faire simple: compte tenu de la gamme de nombres (0,1,2) choisissez un numéro de 0 a 80% de probabilité d'être sélectionné, de 1 a 10% de chances et de 2 a 10% de chances.
Cela fait environ 8 ans que mon collège stats de classe, vous pouvez donc imaginer la bonne formule pour que cela m'échappe pour le moment.
Ici est le "pas cher et sale" la méthode que j'ai trouvé. Cette solution utilise ColdFusion. Le vôtre peut utiliser n'importe quelle langue que vous souhaitez. Je suis un programmeur, je pense que je peux poignée de portage. Finalement ma solution a besoin d'être en Groovy - j'ai écrit celui-ci dans ColdFusion parce que c'est facile à écrire rapidement/test CF.
public function weightedRandom( Struct options ) {
var tempArr = [];
for( var o in arguments.options )
{
var weight = arguments.options[ o ] * 10;
for ( var i = 1; i<= weight; i++ )
{
arrayAppend( tempArr, o );
}
}
return tempArr[ randRange( 1, arrayLen( tempArr ) ) ];
}
//test it
opts = { 0=.8, 1=.1, 2=.1 };
for( x = 1; x<=10; x++ )
{
writeDump( weightedRandom( opts ) );
}
Je suis à la recherche de meilleures solutions, veuillez suggérer des améliorations ou des solutions de rechange.
- Semblable, stackoverflow.com/questions/20586620/...
Vous devez vous connecter pour publier un commentaire.
Rejet d'échantillonnage (comme dans votre solution) est la première chose qui vient à l'esprit, permettant de construire une table de correspondance avec des éléments peuplée par leur poids, de la distribution, puis choisissez un endroit aléatoire dans le tableau et de le retourner. Comme une mise en œuvre le choix, je ferais un ordre supérieur de la fonction qui prend un spec et retourne une fonction qui renvoie des valeurs basé sur la distribution de la spécification, de cette façon, vous éviter d'avoir à construire le tableau pour chaque appel. Les inconvénients sont que l'algorithmique de la performance de la construction de la table est linéaire en le nombre d'éléments et il pourrait être beaucoup de l'utilisation de la mémoire pour les grandes spécifications (ou ceux avec des membres avec de très petites ou précise en poids, par exemple {0:0.99999, 1:0.00001}). L'avantage est que la cueillette d'une valeur de constante de temps, ce qui peut être souhaitable si la performance est critique. En JavaScript:
Une autre stratégie consiste à choisir un nombre au hasard dans
[0,1)
et itérer sur la spécification de poids en additionnant le poids, si le nombre aléatoire est inférieur à la somme puis de retourner la valeur associée. Bien sûr, cela suppose que la somme des poids pour une. Cette solution n'a pas de coûts initiaux, mais a moyen algorithmique de performance linéaire selon le nombre d'entrées dans la spec. Par exemple, en JavaScript:log n
binaire de recherche chaque fois que vous générez un nombre. Mais cela n'a de sens que pour n grand.weightedRand(...)
fonction de la réponse et essayer de comprendre d'où il serait logique d'utiliser de 1000 au lieu de 10...Générer un nombre aléatoire R entre 0 et 1.
Si R dans [0, 0.1) -> 1
Si R dans [0.1, 0.2) -> 2
Si R dans [0.2, 1] -> 3
Si vous ne pouvez pas obtenir un nombre entre 0 et 1, de générer un nombre dans une fourchette qui va produire autant de précision que vous souhaitez. Par exemple, si vous avez le poids de
(1, 83.7%) et (2, 16.3%), déploiement d'un nombre de 1 à 1000. 1-837 est 1. 838-1000 est 2.
C'est plus ou moins générique, isée version de ce @trinithis écrit en Java: je l'ai fait avec des entiers plutôt que des flotteurs pour éviter le désordre des erreurs d'arrondi.
Voici 3 solutions en javascript car je ne suis pas sûr de la langue que vous voulez dans. Selon vos besoins, l'un des deux premiers pourraient travailler, mais le troisième est probablement le plus simple à mettre en œuvre avec de grands ensembles de nombres.
Comment sur
int [ ] nombres = { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 2 } ;
ensuite, vous pouvez sélectionner de manière aléatoire à partir des numéros et 0 aura 80% de chance, 1 à 10%, et de 2 à 10%
J'utilise la suite
C'est mon go-to "pondéré" aléatoire, où j'utilise une fonction inverse de "x" (où x est aléatoire entre min et max) pour générer une pondéré résultat, où le minimum est le plus lourd de l'élément, et le maximum le plus léger (moins de chances d'obtenir le résultat)
Donc, fondamentalement, à l'aide de
weightedRandom(1, 5)
signifie que les chances d'obtenir un 1 sont plus élevés que 2 qui sont plus élevés que d'un 3, ce qui est supérieur à 4, qui sont supérieure à 5.Pourrait ne pas être utile pour votre cas d'utilisation, mais sans doute utile pour les personnes googler cette même question.
Après 100 itérations essayer, il m'a donné:
weightedRandom(50, 100)
mais encore reçu de 1s et un tel, j'ai évidemment raté le point.f(x)=1/x
... (2) étant donné qu'il utilise aléatoire, il n'y a aucune garantie qu'il va utiliser au moins une fois chaque numéro... et (3) le dernier mais non le moindre, vous devez utiliser49 + weightedRandom(1, 51)
si vous souhaitez obtenir des nombres entre 50 et 10049 + weightedRandom(1, 51)
est donc la solution la plus évidente. Je vous remercie.Celui-ci est en Mathematica, mais il est facile de copier dans une autre langue, je l'utilise dans mes jeux et il peut gérer décimal des poids:
(Maintenant je parle avec une liste d'abord l'élément d'indice est égal à 0) L'idée derrière cela est que le fait d'avoir une liste normalisée poids il y a une chance de poids[n] pour revenir à l'index n, de sorte que les distances entre le min et le max à l'étape n devrait être poids[n]. La distance totale à partir du minimum min (qui nous l'avons mis à 0) et le maximum de max est la somme de la liste poids.
La bonne chose derrière cela est que vous n'avez pas à ajouter à n'importe quel tableau ou le nid de boucles, et qui augmente fortement le temps d'exécution.
Voici le code en C#, sans avoir besoin de normaliser la poids liste et la suppression de certains code:
ici à l'entrée et ratios : 0 (80%), 1(10%) , 2 (10%)
permet de sortir donc facile à visualiser.
permet d'ajouter le poids total et de l'appeler pour TR ratio total. donc, dans ce cas, 100.
laisse au hasard un nombre de (0-TR) ou (de 0 à 100 dans ce cas) . 100 votre poids total. Appeler RN de nombre aléatoire.
alors maintenant, nous avons TR comme le poids total et la RN comme le nombre aléatoire entre 0 et TR.
donc permet de l'imaginer, nous avons sélectionné un random # de 0 à 100. Dire 21. donc c'est effectivement de 21%.
NOUS DEVONS NOUS CONVERTIR/CE MATCH À NOTRE ENTRÉE DE CHIFFRES, MAIS COMMENT ?
permet une boucle sur chaque poids (80, 10, 10) et de garder la somme des coefficients de pondération, nous avons déjà visiter.
le moment où la somme des coefficients de pondération, nous sommes en boucle de plus de supérieure à le nombre aléatoire RN (21 dans ce cas), on arrête la boucle & retour que la position de l'élément.
permet de dire que le nombre aléatoire (entre 0 et 100) est de 83. Permet de le faire à nouveau:
8 ans de retard, mais voici ma solution en 3 lignes.
1) Préparer un tableau de de probabilité de la fonction de masse tels que
pmf[array_index] = P(X=array_index):
2) Préparer un tableau pour le correspondant la fonction de distribution cumulée tels que
cdf[array_index] = F(X=array_index):
3a) Générer un nombre aléatoire.
3b) pour Obtenir un tableau des éléments qui sont plus ou égal à ce nombre.
3c) de Retour de sa longueur.
Je suggère d'utiliser un contrôle continu de la probabilité et le reste du nombre aléatoire.
Cette fonction définit d'abord la valeur de retour pour le dernier indice possible et itère jusqu'à ce que le reste de la valeur aléatoire est plus petite que la probabilité réelle.
Les probabilités ont pour somme à un.
JS:
CSS:
J'ai un slotmachine et j'ai utilisé le code ci-dessous pour générer des nombres aléatoires. Dans probabilitiesSlotMachine les touches sont de sortie dans la slotmachine, et les valeurs représentent le poids.
Maintenant à la génération aléatoire de sortie, j'utilise ce code: