L'algorithme est simple

rand_no = rand(0,1)
for each element in array 
     if(rand_num < element.probablity)
          select and break
     rand_num = rand_num - element.probability

un exemple dans ruby

#each element is associated with its probability
a = {1 => 0.25 ,2 => 0.5 ,3 => 0.2, 4 => 0.05}

#at some point, convert to ccumulative probability
acc = 0
a.each { |e,w| a[e] = acc+=w }

#to select an element, pick a random between 0 and 1 and find the first   
#cummulative probability that's greater than the random number
r = rand
selected = a.find{ |e,w| w>r }

p selected[0]

cela peut être fait en O(1) temps prévu par échantillon comme suit.

calcule le CDF F(i) pour chaque élément i comme étant la somme des probabilités inférieures ou égales à I.

Définir la gamme r(i) d'un élément i de l'intervalle [F(i - 1), F(i)].

pour chaque intervalle [(i - 1)/n, i/n], créer un seau composé de la liste des éléments dont l'intervalle chevauche l'intervalle. Cela prend O (n) temps au total pour la pleine tableau aussi longtemps que vous êtes assez prudent.

quand vous échantillonnez au hasard le tableau, vous calculez simplement dans quel seau le nombre aléatoire est, et comparez avec chaque élément de la liste jusqu'à ce que vous trouviez l'intervalle qui le contient.

le coût d'un échantillon est O(La longueur attendue d'une liste choisie au hasard) <= 2.

j'ai trouvé cet article être le plus utile pour comprendre pleinement ce problème. cette question est peut-être aussi ce que vous cherchez.

je crois que la solution optimale est d'utiliser la méthode Alias (wikipedia) . Elle exige O(n) temps pour initialiser, O(1) le temps de faire une sélection, et O(n) memory.

Voici l'algorithme pour générer le résultat du laminage d'une matrice pondérée n (de là, il est trivial de choisir un élément d'une longueur- n array) comme prendre de cet article . L'auteur suppose que vous avez des fonctions pour rouler un dé juste ( floor(random() * n) ) et renverser une pièce biaisée ( random() < p ).

Algorithme: méthode D'Alias de Vose

initialisation:

1. Créer des tableaux Alias et Prob , chacun de taille n .
2. créer deux listes de travail, petit et grand .
3. multiplier chaque Probabilité par n .
4. pour chaque probabilité graduée p _i :
   1. Si p _je < 1 , ajouter je à Petits .
   2. dans le cas Contraire ( p _je ≥ 1 ), ajouter je à Grand .
5. alors que petit et grand ne sont pas vides: ( grand pourrait être vidé d'abord)
   1. supprimer le premier élément de petit ; l'appeler l .
   2. Supprimer le premier élément de Grand ; l'appeler g .
   3. Set Prob[l] = p _l .
   4. Set Alias [l] = g .
   5. Set p _g : = (p _g +p _l ) -1 . (C'est une option numériquement plus stable.)
   6. si p _g <1 , ajouter g à petit .
   7. autrement ( p _g ≥ 1 ), ajouter g à Large .
6. alors que Large n'est pas vide:
   1. Supprimer le premier élément de Grand ; l'appeler g .
   2. Set Prob[g] = 1 .
7. alors que Small n'est pas vide: cela est seulement possible en raison de l'instabilité numérique.
   1. supprimer le premier élément de petit ; l'appeler l .
   2. Set Prob[l] = 1 .

Génération:

1. Générer une juste lancer de dé à partir d'un n dérapé meurt; appelez le côté je .
2. Flip un biaisée pièce, qui est pile avec une probabilité Prob[i] .
3. si la pièce apparaît "têtes", "retour i .
4. sinon, retourner Alias [i] .

autre exemple de rubis:

def weighted_rand(weights = {})
  raise 'Probabilities must sum up to 1' unless weights.values.inject(&:+) == 1.0
  raise 'Probabilities must not be negative' unless weights.values.all? { |p| p >= 0 }
  # Do more sanity checks depending on the amount of trust in the software component using this method
  # E.g. don't allow duplicates, don't allow non-numeric values, etc.

  # Ignore elements with probability 0
  weights = weights.reject { |k, v| v == 0.0 }   # e.g. => {"a"=>0.4, "b"=>0.4, "c"=>0.2}

  # Accumulate probabilities and map them to a value
  u = 0.0
  ranges = weights.map { |v, p| [u += p, v] }   # e.g. => [[0.4, "a"], [0.8, "b"], [1.0, "c"]]

  # Generate a (pseudo-)random floating point number between 0.0(included) and 1.0(excluded)
  u = rand   # e.g. => 0.4651073966724186

  # Find the first value that has an accumulated probability greater than the random number u
  ranges.find { |p, v| p > u }.last   # e.g. => "b"
end

comment utiliser:

weights = {'a' => 0.4, 'b' => 0.4, 'c' => 0.2, 'd' => 0.0}

weighted_rand weights

à Quoi s'attendre:

d = 1000.times.map{ weighted_rand weights }
d.count('a') # 396
d.count('b') # 406
d.count('c') # 198

Ruby solution à l'aide de la pick-up gem :

require 'pickup'

chances = {0=>80, 1=>20}
picker = Pickup.new(chances)

exemple:

5.times.collect {
  picker.pick(5)
}

a donné la sortie:

[[0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 1, 1], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 1]]

si le tableau est petit, je donnerais au tableau une longueur de, dans ce cas, cinq et assignerais les valeurs appropriées:

array[
    0 => 0
    1 => 0
    2 => 0
    3 => 0
    4 => 1
]

c'est un code PHP que j'ai utilisé dans la production:

/**
 * @return \App\Models\CdnServer
*/
protected function selectWeightedServer(Collection $servers)
{
    if ($servers->count() == 1) {
        return $servers->first();
    }

    $totalWeight = 0;

    foreach ($servers as $server) {
        $totalWeight += $server->getWeight();
    }

    // Select a random server using weighted choice
    $randWeight = mt_rand(1, $totalWeight);
    $accWeight = 0;

    foreach ($servers as $server) {
        $accWeight += $server->getWeight();

        if ($accWeight >= $randWeight) {
            return $server;
        }
    }
}

le truc pourrait être d'échantillonner un tableau auxiliaire avec des répétitions d'éléments qui reflètent la probabilité

étant donné les éléments associés à leur probabilité, en pourcentage:

h = {1 => 0.5, 2 => 0.3, 3 => 0.05, 4 => 0.05 }

auxiliary_array = h.inject([]){|memo,(k,v)| memo += Array.new((100*v).to_i,k) }   

ruby-1.9.3-p194 > auxiliary_array 
 => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,                                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4] 

auxiliary_array.sample

si vous voulez être aussi générique que possible, vous devez calculer le multiplicateur basé sur le nombre maximum de chiffres fractionnaires, et l'utiliser à la place de 100:

m = 10**h.values.collect{|e| e.to_s.split(".").last.size }.max

j'imagine que les nombres supérieurs ou égaux à 0,8 mais inférieurs à 1,0 sélectionnent le troisième élément.

en d'autres termes:

x est un nombre aléatoire entre 0 et 1

si 0,0 >= x < 0,2 : rubrique 1

si 0.2 >= x < 0.8 : rubrique 2

si 0.8 >= x < 1.0: Rubrique 3

je vais améliorer https://stackoverflow.com/users/626341/masciugo réponse.

Fondamentalement, vous faire un grand tableau où le nombre de fois qu'un élément s'affiche est proportionnelle au poids.

il a quelques inconvénients.

1. Le poids peut ne pas être entier. Supposons que l'élément 1 ait une probabilité d'IP et que l'élément 2 ait une probabilité d'IP-1. Comment répartissez-vous que? Ou imaginez si il y a des centaines de ces éléments.
2. Le tableau créé peut être très grande. Imaginez si le multiplicateur le moins commun est 1 million, alors nous aurons besoin d'un tableau de 1 million d'éléments dans le tableau que nous voulons choisir.

Pour contrer cela, c'est ce que vous faites.

crée un tel tableau, mais insère seulement un élément au hasard. La probabilité qu'un élément soit inséré est proportionnelle au poids.

alors sélectionnez l'élément aléatoire de d'habitude.

donc s'il y a 3 éléments avec des poids différents, vous choisissez simplement un élément d'un tableau de 1-3 éléments.

des problèmes peuvent se poser si l'élément construit est vide. C'est juste qu'il arrive qu'aucun élément n'apparaisse dans le tableau parce que leurs dés roulent différemment.

dans ce cas, je propose que la probabilité qu'un élément soit inséré soit p(inséré)=wi/wmax.

De cette façon, un élément, à savoir celui qui a la plus grande probabilité, sera inséré. Les autres éléments seront insérés par la probabilité relative.

disons que nous avons 2 objets.

l'élément 1 apparaît .20% du temps. l'élément 2 apparaît .40% du temps et a la plus grande probabilité.

à thearray, l'élément 2 apparaîtra tout le temps. Élément 1 montrera la moitié du temps.

ainsi, l'élément 2: être appelé 2 fois plus que l'élément 1. Pour la généralité tous les autres éléments seront appelés proportionnels à leur poids. Aussi la somme de leur probabilité de 1, parce que le tableau aura toujours au moins 1 élément.