Generieren Sie eine gewichtete Zufallszahl

Ich versuche, einen (guten) Weg zu finden, um eine Zufallszahl aus einer Reihe möglicher Zahlen auszuwählen, bei der jeder Zahl in der Reihe ein Gewicht gegeben wird. Um es einfach auszudrücken: Wählen Sie in Anbetracht des Zahlenbereichs (0,1,2) eine Zahl, bei der 0 eine Wahrscheinlichkeit von 80 % hat, ausgewählt zu werden, 1 eine Wahrscheinlichkeit von 10 % und 2 eine Wahrscheinlichkeit von 10 % hat.

Es ist ungefähr 8 Jahre her seit meinem College-Statistikkurs, also können Sie sich vorstellen, dass mir die richtige Formel dafür im Moment entgeht.

Hier ist die “billige und schmutzige” Methode, die ich mir ausgedacht habe. Diese Lösung verwendet ColdFusion. Ihre können die Sprache verwenden, die Sie möchten. Ich bin ein Programmierer, ich denke, ich kann damit umgehen, es zu portieren. Letztendlich muss meine Lösung in Groovy sein – ich habe diese in ColdFusion geschrieben, weil es einfach ist, schnell in CF zu schreiben/testen.

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 ) );    
}

Ich suche nach besseren Lösungen, bitte schlagen Sie Verbesserungen oder Alternativen vor.

Ablehnungsprobenahme (wie in Ihrer Lösung) ist das erste, was mir in den Sinn kommt, wobei Sie eine Nachschlagetabelle mit Elementen erstellen, die durch ihre Gewichtsverteilung gefüllt sind, dann eine zufällige Position in der Tabelle auswählen und zurückgeben. Als Implementierungsoption würde ich eine Funktion höherer Ordnung erstellen, die eine Spezifikation übernimmt und eine Funktion zurückgibt, die Werte basierend auf der Verteilung in der Spezifikation zurückgibt. Auf diese Weise vermeiden Sie, dass Sie die Tabelle für jeden Aufruf erstellen müssen. Die Nachteile sind, dass die algorithmische Leistung beim Erstellen der Tabelle linear zur Anzahl der Elemente ist und dass möglicherweise viel Speicher für große Spezifikationen verwendet wird (oder solche mit Mitgliedern mit sehr kleinen oder präzisen Gewichtungen, z. B. {0:0,99999, 1 :0.00001}). Der Vorteil ist, dass die Auswahl eines Werts eine konstante Zeit hat, was wünschenswert sein kann, wenn die Leistung kritisch ist. In JavaScript:

function weightedRand(spec) {
  var i, j, table=[];
  for (i in spec) {
    // The constant 10 below should be computed based on the
    // weights in the spec for a correct and optimal table size.
    // E.g. the spec {0:0.999, 1:0.001} will break this impl.
    for (j=0; j<spec[i]*10; j++) {
      table.push(i);
    }
  }
  return function() {
    return table[Math.floor(Math.random() * table.length)];
  }
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});
rand012(); // random in distribution...

Eine andere Strategie besteht darin, eine zufällige Zahl auszuwählen [0,1) and iterate over the weight specification summing the weights, if the random number is less than the sum then return the associated value. Of course, this assumes that the weights sum to one. This solution has no up-front costs but has average algorithmic performance linear by the number of entries in the spec. For example, in JavaScript:

function weightedRand2(spec) {
  var i, sum=0, r=Math.random();
  for (i in spec) {
    sum += spec[i];  if (r <= sum) return i;  } } weightedRand2({0:0.8, 1:0.1, 2:0.1});  // zufällig in Verteilung...

Generieren Sie eine Zufallszahl R zwischen 0 und 1.

Wenn R drin ist [0, 0.1) -> 1

If R in [0.1, 0.2) -> 2

If R in [0.2, 1] -> 3

Wenn Sie eine Zahl zwischen 0 und 1 nicht direkt erhalten können, generieren Sie eine Zahl in einem Bereich, der so viel Genauigkeit erzeugt, wie Sie möchten. Zum Beispiel, wenn Sie die Gewichte für haben

(1, 83,7 %) und (2, 16,3 %) würfeln eine Zahl von 1 bis 1000. 1-837 ist eine 1. 838-1000 ist eine 2.

Ich verwende folgendes

function weightedRandom(min, max) {
  return Math.round(max / (Math.random() * max + min));
}

Dies ist mein "gewichteter" Zufall, bei dem ich eine Umkehrfunktion von "x" verwende (wobei x ein Zufall zwischen min und max ist), um ein gewichtetes Ergebnis zu generieren, bei dem das Minimum das schwerste Element und das Maximum ist das leichteste (geringste Chancen, das Ergebnis zu erhalten)

Also im Grunde mit weightedRandom(1, 5) bedeutet, dass die Chancen, eine 1 zu bekommen, höher sind als eine 2, die höher sind als eine 3, die höher sind als eine 4, die höher sind als eine 5.

Könnte für Ihren Anwendungsfall nicht nützlich sein, aber wahrscheinlich nützlich für Leute, die dieselbe Frage googeln.

Nach 100 Iterationen hat es mir Folgendes gegeben:

==================
| Result | Times |
==================
|      1 |    55 |
|      2 |    28 |
|      3 |     8 |
|      4 |     7 |
|      5 |     2 |
==================

Hier sind 3 Lösungen in Javascript, da ich nicht sicher bin, in welcher Sprache Sie es haben möchten. Abhängig von Ihren Anforderungen könnte eine der ersten beiden funktionieren, aber die dritte ist wahrscheinlich am einfachsten mit großen Mengen von Zahlen zu implementieren.

function randomSimple(){
  return [0,0,0,0,0,0,0,0,1,2][Math.floor(Math.random()*10)];
}

function randomCase(){
  var n=Math.floor(Math.random()*100)
  switch(n){
    case n<80:
      return 0;
    case n<90:
      return 1;
    case n<100:
      return 2;
  }
}

function randomLoop(weight,num){
  var n=Math.floor(Math.random()*100),amt=0;
  for(var i=0;i<weight.length;i++){
    //amt+=weight[i]; *alternative method
    //if(n<amt){
    if(n<weight[i]){
      return num[i];
    }
  }
}

weight=[80,90,100];
//weight=[80,10,10]; *alternative method
num=[0,1,2]

Dies ist mehr oder weniger eine generische Version dessen, was @trinithis in Java geschrieben hat: Ich habe es mit Ints statt Floats gemacht, um unordentliche Rundungsfehler zu vermeiden.

static class Weighting {

    int value;
    int weighting;

    public Weighting(int v, int w) {
        this.value = v;
        this.weighting = w;
    }

}

public static int weightedRandom(List<Weighting> weightingOptions) {

    //determine sum of all weightings
    int total = 0;
    for (Weighting w : weightingOptions) {
        total += w.weighting;
    }

    //select a random value between 0 and our total
    int random = new Random().nextInt(total);

    //loop thru our weightings until we arrive at the correct one
    int current = 0;
    for (Weighting w : weightingOptions) {
        current += w.weighting;
        if (random < current)
            return w.value;
    }

    //shouldn't happen.
    return -1;
}

public static void main(String[] args) {

    List<Weighting> weightings = new ArrayList<Weighting>();
    weightings.add(new Weighting(0, 8));
    weightings.add(new Weighting(1, 1));
    weightings.add(new Weighting(2, 1));

    for (int i = 0; i < 100; i++) {
        System.out.println(weightedRandom(weightings));
    }
}

8 Jahre zu spät, aber hier ist meine Lösung in 4 Zeilen.

1. Bereiten Sie eine Reihe von vor Wahrscheinlichkeit Massenfunktion so dass

pmf[array_index] = P(X=Array_Index):

var pmf = [0.8, 0.1, 0.1]

2. Bereiten Sie ein Array für das entsprechende vor Verteilungsfunktion so dass

cdf[array_index] = F(X=Array_Index):

var cdf = pmf.map((sum => value => sum += value)(0))
// [0.8, 0.9, 1]

3a) Erzeuge eine Zufallszahl.

3b) Holen Sie sich ein Array von Elementen, die größer oder gleich dieser Zahl sind.

3c) Gib seine Länge zurück.

var r = Math.random()
cdf.filter(el => r >= el).length

Wie wäre es mit

int [ ] Zahlen = {0, 0, 0, 0, 0, 0, 0, 0, 1, 2};

dann können Sie zufällig aus Zahlen auswählen und 0 hat eine Chance von 80 %, 1 10 % und 2 10 %