循環遍歷隨機排序數組時的概率算法

Question

我認爲，通過查看代碼，問題非常簡單。我有一個隨機陣列（數組必須被隨機化，一些代碼已被排除，因爲它不涉及實際問題，但確實需要隨機化）。對於數組中的每個元素，都有一個「概率」索引（這裏將其描述爲值本身，在$rules中），假設提示如果滿足其他條件（爲了不相關而刪除）時，概率數組元素將被「觸發」（在這種情況下，該陣列元件的得分將遞增1）

考慮代碼：

<?php 
    // Taken from php.net/shuffle user notes 
    // Shuffles an array order for the sake of foreach while maintaining 
    // key => value associations 
    function shuffle_assoc(&$array) { 
    $keys = array_keys($array); 
    shuffle($keys); 
    foreach($keys as $key) { 
     $new[$key] = $array[$key]; 
    } 
    return $new; 
    } 

    $i = 1000000; // How many tests to perform 

    // This is my rule list. Each key is a simple color 
    // and each value is a probability represented as a percent 
    $rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

    // Initialize the scores array with all 0's 
    // The "outs" will be used when the probability does not 
    // occur in any of the rules 
    $scores = array('outs' => 0); 
    foreach($rules as $k => $v) { 
    $scores[$k] = 0; 
    } 

    $count = count($rules); 

    for($x = 0; $x < $i; $x++) { 
    $rules = shuffle_assoc($rules); 

    foreach($rules as $k => $probability) { 
     $rand = mt_rand(1,100); 
     //$probability = ??; I've tried applying many different operations here to "correct" the probability 

     if($rand > $probability) { 
     continue; 
     } else { 
     $scores[$k]++; 
     continue 2; 
     } 
    } 
    $scores['outs']++; 
    } 


    foreach($scores as $k => $v) { 
    echo "$k: " . (($v/$i)*100) . "% ($v/$i)\n"; 
    } 

?> 

預期輸出（僞）。注意百分比對應與$rules

outs: less than 1% (.../1000000) 
black: 20% (.../1000000) 
white: 10% (.../1000000) 
red: 40% (.../1000000) 
green: 5% (.../1000000) 
blue: 25% (.../1000000) 

例輸出值：

outs: 30.7128% (307128/1000000) 
black: 13.2114% (132114/1000000) 
white: 6.3381% (63381/1000000) 
red: 29.5247% (295247/1000000) 
green: 3.1585% (31585/1000000) 
blue: 17.0545% (170545/1000000) 

事情我已經試過&注意事項：

• 正如你所看到的，我環路內有一個$probability = ??的註釋部分，我嘗試了各種明顯的計算每個實際可能性的方法元素，包括玩$count（規則數量），這就是爲什麼該變量存在和未使用。

• 它不一定非常確切，但最好在較小的一組數字上（e.x. 1,000次迭代）具有穩定的結果。

• 它可能很模糊。 +/- 5％的變化不會傷害我的感覺，特別是在較少的迭代次數中，我理解大數理論在這裏起作用。

• 只要它們低於1％-2％，出貨次數並不是什麼大不了的。我也嘗試用各種方法消除缺口，以確定是否單獨出現歪斜，有趣的是，當我有一次這樣做時，我得到了全部20％的分裂（即使是）。此外，在「出局」時，我能夠非常少的出場，通過基本強制性的概率「數字」（也就是，$rules的值）從100開始倒退，能夠非常接近正確的分組。 ，但我從來沒有找到一個精確的，最佳的方法。每一次，我都會接近一種顏色的結果，這會使其他顏色在小但明顯的範圍內傾斜。這些數字並沒有易於我掌握的相關性，似乎是隨機的，儘管很明顯結果在概率與大數之間表現良好。

告訴我有一個確切的方法來計算這個。這讓我瘋狂。

編輯：我有我的代碼已敲定的版本，從下面的兩個答案的幫助下，做這個工作，而不需要知道概率百分比循環開始前，並沒有額外的或嵌套循環（這是我特別需要的，我想我應該在那部分中更直接）。從每個迭代的角度來說，您可以根據該特定迭代的屬性動態地提取概率。這裏的所有答案都是無價的，這裏是我的版本的最終代碼：http://pastebin.com/eB3TVP1E

Answer 1

在你的代碼中實現傑克的想法（如果概率之和爲> 100，這將不起作用）：

php fiddle

<?php 
    // Taken from php.net/shuffle user notes 
    // Shuffles an array order for the sake of foreach while maintaining 
    // key => value associations 
    function shuffle_assoc(&$array) { 
    $keys = array_keys($array); 
    shuffle($keys); 
    foreach($keys as $key) { 
     $new[$key] = $array[$key]; 
    } 
    return $new; 
    } 

    $i = 1000000; // How many tests to perform 

    // This is my rule list. Each key is a simple color 
    // and each value is a probability represented as a percent 
    $rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

    // Initialize the scores array with all 0's 
    // The "outs" will be used when the probability does not 
    // occur in any of the rules 
    $scores = array('outs' => 0); 
    foreach($rules as $k => $v) { 
    $scores[$k] = 0; 
    } 

    $count = count($rules); 
//$limits is what Jack called $rules_norm 
$limits=array(); 
$limit=0; 
foreach($rules as $k=>$v) 
{ 
    $limit+=$v; 
    $limits[$k]=$limit; 
} 
    for($x = 0; $x < $i; $x++) { 
     $rand = mt_rand(1,100); 
foreach($limits as $k=>$v) 
{ 
    if($v>=$rand) 
    { 
     $scores[$k]++; 
     continue(2); 
    } 

} 
    $scores['outs']++; 
    } 


    foreach($scores as $k => $v) { 
    echo "$k: " . (($v/$i)*100) . "% ($v/$i)\n"; 
    } 

?> 

Answer 2

只是規範化結果，積累他們，然後你就完成了。

我的意思是：

• 總和爲陣，以獲得總的每一個項目提供的所有可能性（這是你的情況100但它很容易一般化）
• 鴻溝每一個概率總

因此，例如：

$rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

將被標準化爲：

$rules_norm = array(
    'black' => 0.2, 
    'white' => 0.1, 
    'red' => 0.4, 
    'green' => 0.05, 
    'blue' => 0.25, 
); 

• 現在積累的結果，這樣在$rules_norm每個元素你計算所有以前的元素加上當前的總和。

所以：

$rules_norm = array(
    'black' => 0.2, 
    'white' => 0.3, 
    'red' => 0.7, 
    'green' => 0.75, 
    'blue' => 1.0, 
); 

這個

現在你可以只提取範圍[0,1)隨機浮點數，並選擇哪些元素增加根據結果：遞增一個元素的成績從剛開始第一個數組中，並增加了一個，使得$rand > $rules_norm[k]