使用概率分佈對數組進行排序

Question

數組應按其值排序從高到低。

<?php 
$items = array(
    1 => f(1), 
    2 => f(2), 
    3 => f(3), 
    4 => f(4), 
    5 => f(5), 
); 
?> 

排序後，我看看哪個項目1,2,3,4,5是第一個。我一遍又一遍地嘗試。 之後

• 5應該是5倍以上，1
• 4應該是四倍以上1
• 3應該是第一項中的第一項中的第一項三次超過1
• 4應該是第一個項目兩次超過2
• ...

一個想法是

<?php 
function f(key) { 
    return key/random(); 
} 
?> 

其中，爲1'000'000嘗試導致

key | times on top | ratio with key one | expected ratio 
----+--------------+--------------------+--------------- 
5 |  374'365 | 6.75    | 5 
4 |  267'863 | 4.83    | 4 
3 |  185'707 | i am so lazy ... | 3 
2 |  116'618 |     | 2 
1 |  55'447 | 1     | 1 

看起來奇怪的我，但也許

• 有以f一個簡單的問題？
• 有更好的f？

---

我的實現：

<?php 

abstract class Test { 

    private $result; 

    protected abstract function f($x); 

    protected function iteration() { 
    $values = array(
     1 => $this->f(1), 
     2 => $this->f(2), 
     3 => $this->f(3), 
     4 => $this->f(4), 
     5 => $this->f(5), 
    ); 

    arsort($values); 

    $top = key($values); 

    if (!isset($this->result[$top])) { 
     $this->result[$top] = 1; 
    } else { 
     $this->result[$top]++; 
    } 
    } 

    public function run($iterations) { 
    $this->result = array(); 
    for($i = 0; $i < $iterations; $i++) { 
     $this->iteration(); 
    } 
    arsort($this->result); 
    return $this->result; 
    } 
} 

class MyTest extends Test { 
    protected function f($x) { 
    return $x/rand(); 
    } 
} 

$test = new MyTest(); 
$result = $test->run(1000 * 1000); 
print_r($result); 
printf("Ratio of key 5 to 1, which should be 5: %f\n", $result[5]/$result[1]); 

?> 

---

我已經嘗試了十億輪。但是再比例是6.75 - 整點是：爲什麼不是五呢？

---

爲

<?php 
class BetterRandomGeneratorTest extends Test { 
    protected function f($x) { 
    return $x/mt_rand(); 
    } 
} 
?> 

的結果是

Array 
(
    [5] => 3742816 
    [4] => 2674352 
    [3] => 1861444 
    [2] => 1168333 
    [1] => 553055 
) 
Ratio of key 5 to 1: 6.767529 

Answer 1

下面是一個簡單˚F這將做到這一點。

function f(key) { 
    $x = 0; 
    for($i = 0; $i < $key; $i++) { 
    $y = random(); 
    if ($x < $y) { 
     $x = $y; 
    } 
    } 
    return $x; 
} 

這是保證工作，因爲max是同樣可能是任何所選擇的15個隨機數字，和1/3的時間，這個數字將在f(5)，與1/15的f(1)。

至於你的f有什麼問題，它很簡單。您的解決方案具有完美的對稱性，正好80％的時間，f(1) < f(5)。但是，當f(1)大於平均值和f(5)小於平均值時，f(1)往往大於f(5)。同上f(2),f(3)和f(4)。然而，f(2), ... f(5)的所有數字一次很小是不常見的。這會導致f(1)的相關性比天真地想象的要少。反之亦然，往往會比天真地想到的更頻繁地出現f(5)。

如果您想要計算每個數字出現在頂部的確切概率，那麼使用積分計算精確答案應該不會太難。這個想法是，你從0到1的積分概率，如果這是random()的值f(i)那f(i)是最大的。 （因此，例如，對於5，您將整合(1-x/5)(1-x/4)(1-x/3)(1-x/2)，而對於1，如果random()大於0.2，則會整合一個爲0的函數，否則爲(1-2x)(1-3x)(1-4x)(1-5x)。）表達式將變得複雜，並且比例不會出來以很好的答案。