Zufall basiert auf Bereich

Question

Ich habe ein Array von Elementen:

$arr = array(
    '0' => 265000, // Area 
    '1' => 190000, 
    '2' => 30000, 
    '3' => 1300 
); 

ich basierten Zufallsindex erhalten möchten auf den Bereich (Array-Wert). Ich muss den Bereich mit großem Wert häufiger auswählen. Wie kann ich das tun?

Was ich habe jetzt:

$random_idx = mt_rand(0, count($arr)-1);  
$selected_area = (object)$arr[$random_idx]; 

Dank!

Answer 1

1. Repeted Werte

Nehmen wir an, wir ein Array haben, in dem jeder Wert auf die relative Wahrscheinlichkeit seines Index entspricht. Zum Beispiel, bei einer Münze, sind die möglichen Ergebnisse eines Tosses 50% Tails und 50% Heads. Wir können diese Wahrscheinlichkeit mit einer Reihe darstellen, wie (ich PHP verwenden werden, da dies die Sprache, die von OP verwendet scheint):

$dice = array('2' => 1, '3' => 2, '4' => 3, '5' => 4, '6' => 5, '7' => 6, 
       '8' => 5, '9' => 4, '10' => 3, '11' => 2, '12' => 1 
); 

:

$coin = array(  
    'head' => 1,  
    'tails' => 1  
); 

Während die Ergebnisse von zwei Würfeln können dargestellt werden als

Ein einfacher Weg, um einen zufälligen Schlüssel (Index) mit einer Wahrscheinlichkeit proportional zu den Werten dieser Arrays (und damit konsistent zum zugrunde liegenden Modell) auszuwählen, ist ein anderes Array zu erstellen, dessen Elemente die Schlüssel des ursprünglichen so oft wiederholen wie durch die Werte angezeigt und dann einen zufälligen Wert zurückgeben. Zum Beispiel für die dice Array:

$arr = array(2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, ... 

Dabei sind wir davon überzeugt, dass jede Taste mit der rechten relativen Wahrscheinlichkeit abgeholt werden. Wir können mit einem constructer in einer Klasse die gesamte Logik kapseln, die die Helfer Array eine Funktion erstellt, die einen zufälligen Index mt_rand() mit zurückgibt:

class RandomKeyMultiple { 
    private $pool = array(); 
    private $max_range; 

    function __construct($source) { 
     // build the look-up array 
     foreach ($source as $key => $value) { 
      for ($i = 0; $i < $value; $i++) { 
       $this->pool[] = $key; 
      } 
     } 
     $this->max_range = count($this->pool) - 1; 
    } 

    function get_random_key() { 
     $x = mt_rand(0, $this->max_range); 

     return $this->pool[$x];  
    } 
} 

Die Nutzung ist einfach, erstellen Sie einfach ein Objekt der Klasse der Quelle vorbei Array und dann wird jeder Aufruf der Funktion wird einen zufälligen Schlüssel zurück:

$test = new RandomKeyMultiple($dice); 
echo $test->get_random_key(); 

Das Problem ist, dass OP der Arrays großen Wert enthält, und dies führt zu einem sehr groß (aber immer noch überschaubar, auch ohne alle Werte von 100 dividiert) Array.

2. Schritte

Im Allgemeinen können diskrete Wahrscheinlichkeitsverteilung komplizierter sein, mit Float-Werte, die nicht leicht in der Anzahl der Wiederholungen übersetzt werden kann.

Eine andere Möglichkeit, das Problem zu lösen ist, die Werte im Array als die misures von Intervallen zu prüfen, die die globale Reichweite aller möglichen Werte teilen:

+---------------------------+-----------------+-------+----+ 
    |       |     |  | | 
    |<---  265000  --->|<-- 190000 -->|<30000>|1300| 
    |<-------   455000   ------>|   | 
    |<----------    485000   --------->| | 
    |<----------------   486300  -------------->| 

Dann können wir eine Zufallszahl zwischen 0 wählen und 486300 (der globale Bereich) und den richtigen Index nachschlagen (dessen Chancen proportional zur Länge seines Segments wären, was die richtige Wahrscheinlichkeitsverteilung ergibt).Etwas wie:

$x = mt_rand(0, 486300); 
if ($x < 265000) 
    return 0; 
elseif ($x < 455000) 
    return 1; 
elseif ($x < 485000) 
    return 2; 
else 
    return 3; 

Wir haben den Algorithmus verallgemeinern kann und kapseln die gesamte Logik in einer Klasse (ein Helfer Array mit den Teilsummen speichern):

class RandomKey { 
    private $steps = array(); 
    private $last_key; 
    private $max_range; 

    function __construct($source) { 
     // sort in ascending order to partially avoid numerical issues 
     asort($source); 

     // calculate the partial sums. Considering OP's array: 
     // 
     // 1300 ---->  0 
     // 30000 ----> 1300 
     // 190000 ----> 31300 
     // 265000 ----> 221300 endind with $partial = 486300 
     // 
     $partial = 0; 
     $temp = 0; 
     foreach ($source as $k => &$v) { 
      $temp = $v; 
      $v = $partial; 
      $partial += $temp; 
     } 

     // scale the steps to cover the entire mt_rand() range 
     $factor = mt_getrandmax()/$partial; 
     foreach ($source as $k => &$v) { 
      $v *= $factor; 
     } 

     // Having the most probably outcomes first, minimizes the look-up of 
     // the correct index 
     $this->steps = array_reverse($source); 

     // remove last element (don't needed during checks) but save the key 
     end($this->steps); 
     $this->last_key = key($this->steps); 
     array_pop($this->steps); 
    } 

    function get_random_key() { 
     $x = mt_rand(); 

     foreach ($this->steps as $key => $value) { 
      if ($x > $value) { 
       return $key; 
      } 
     } 
     return $this->last_key;  
    } 

} 

Here oder here gibt es Live-Demos mit einige Beispiele und Hilfsfunktionen, um die Wahrscheinlichkeitsverteilung der Schlüssel zu überprüfen.

Bei größeren Arrays kann auch eine binäre Suche zur Suche nach dem Index in Betracht gezogen werden.

Answer 2

Diese Lösung basiert auf dem Index des Elements, nicht auf seinem Wert. Wir müssen also das Array so ordnen, dass es immer sicher ist, dass das Element mit dem größeren Wert einen größeren Index hat.

(y) 

a i  4    + 
r n  3   + 
r d  2  + 
a e  1 + 
y x  0 + 
      0 1 2 3 4  

      r a n d o m 
      n u m b e r (x) 

Wir brauchen Indizes zu erzeugen, nicht-linear (größerer Index - mehr Wahrscheinlichkeit):

Zufallsindexgenerator kann nun als lineare Abhängigkeit x = y dargestellt wird

a i  4        + + + + + 
r n  3     + + + + 
r d  2   + + + 
a e  1 + + 
y x  0 + 
      0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 

      r a n d o m 
      n u m b e r 

Für die Bereich von x Werte für ein Array der Länge c können wir die Summe aller Zahlen im Bereich 0..c:

berechnen

Um x für jede y finden wir quadratische Gleichung lösen

y^2 + y - 2 * x = 0; 

Nachdem das wir bekommen

y = (sqrt(8 * x + 1) - 1)/2; 

nun gelöst seien wir alle zusammen:

$c = $count($arr); 
$range = ($c * ($c + 1))/2; 
$random_x = mt_rand(0, range); 
$random_idx = floor((sqrt(8 * $random_x + 1) - 1)/2); 

Diese Lösung passt am besten für große Arrays in Bezug auf die Leistung - es d Es hängt nicht von der Größe und dem Typ des Arrays ab.

Answer 3

Ihr Array beschreibt eine diskrete Wahrscheinlichkeitsverteilung. Jeder Array-Wert ('Bereich' oder 'Gewicht') bezieht sich auf die Wahrscheinlichkeit, dass eine diskrete Zufallsvariable einen bestimmten Wert aus dem Bereich der Array-Schlüssel nimmt.

/** 
* Draw a pseudorandom sample from the given discrete probability distribution. 
* The input array values will be normalized and do not have to sum up to one. 
* 
* @param array $arr Array of samples => discrete probabilities (weights). 
* @return sample 
*/ 
function draw_discrete_sample($arr) { 
    $rand = mt_rand(0, array_sum($arr) - 1); 
    foreach ($arr as $key => $weight) { 
     if (($rand -= $weight) < 0) return $key; 
    } 
} 

Ersetzen Sie die erste Zeile mit $rand = mt_rand()/mt_getrandmax() * array_sum($arr);, wenn Sie nicht-ganzzahligen Gewichten/Wahrscheinlichkeiten unterstützen wollen.

Vielleicht möchten Sie sich auch ähnliche Fragen ansehen asked here. Wenn Sie nur an einer kleinen Menge bekannter Verteilungen interessiert sind, empfehle ich den analytischen Ansatz outlined by Oleg Mikhailov.

Answer 4

Dieses Problem ähnelt der Art, wie Betriebssysteme den nächsten Thread identifizieren können, der mit lottery scheduling ausgeführt werden soll.

Die Idee besteht darin, jedem Bereich eine Anzahl von Tickets zuzuordnen, abhängig von seiner Größe und Anzahl dieser Tickets. Abhängig davon, welche Zufallszahl gewählt wurde, wissen Sie, welches Ticket gewonnen wurde und somit das Gewinngebiet.

Zuerst müssen Sie alle Bereiche zusammenfassen und bis zu dieser Summe eine Zufallszahl finden. Jetzt iterieren Sie einfach durch Ihr Array und suchen nach dem ersten Element, dessen Summe bis zu diesem Punkt größer ist als die Zufallszahl.

Angenommen, Sie suchen nach einer Lösung in PHP:

function get_random_index($array) { 
    // generate total 
    $total = array_sum($array); 
    // get a random number in the required range 
    $random_number = rand(0, $total-1); 
    // temporary sum needed to find the 'winning' area 
    $temp_total = 0; 
    // this variable helps us identify the winning area 
    $current_area_index = 0; 

    foreach ($array as $area) { 
     // add the area to our temporary total 
     $temp_total = $temp_total + $area; 

     // check if we already have the right ticket 
     if($temp_total > $random) { 
      return $current_area_index; 
     } 
     else { 
      // this area didn't win, so check the next one 
      $current_area_index++; 
     } 
    } 
}