隨機選擇，按職級

加權比方說，我有ň對象的集合，而且每個對象都有與之相關聯的排名，而這些排名通過ň對應的整數值1。隨機選擇，按職級

現在假設我想從集合中隨機選擇一個對象。但我不想隨便選一個從1到n的數字;相反，我想這樣做的目的是讓我更有可能在名單上選一個更高的數字（排名接近1）。

提議的解決方案：而不是從1到採摘Ñ，挑從1到米，其中米是一些數顯著大於Ñ;然後使用一些映射功能f：[1,m]→[1,n]，其將較多數字映射到較高等級而不是較低等級。例如，˚F（1），˚F（2），˚F（3）可能所有返回1，而˚F（m）爲映射到Ñ唯一的一個，因此它爲三次數更可能得到1比n。希望這是有道理的。

所以我的問題是：如果這似乎是一個合理的算法，什麼是合理的功能˚F完成此，並且什麼比米/ N將足夠大，整數四捨五入並不妨礙人數從永遠被採摘？

[在我的特殊情況下，n可能相當大（數以千計），所以像here這樣的解決方案對於這種情況不太實際。此外，選擇是「與替換」;即我選擇一個對象一次然後返回;我不在乎下一次是否立即再次選取它。]

來源

2011-05-03 Andrew Arnold

看到這個答案：http://stackoverflow.com/questions/1761626/weighted-random-numbers/1761646#1761646 – 2011-05-03 16:00:12

你可以做類似如下：

double bias = 1.5; 
int index = (int)(n * (bias - sqrt(bias*bias -4.0*(bias-1.0)* random())) 
       /2.0/(bias-1));

改變偏置參數讓你控制強烈支持較高等級的人。

編輯：下面是它的一些Python代碼。

def pick(n, bias): 
    return int(n * (bias - sqrt(bias*bias -4.0*(bias-1.0)*random()))/2.0/(bias-1)) 

vals = [0]*10 
for i in xrange(1000): 
    vals[pick(10,1.5)] += 1 
print vals 
[153, 151, 115, 116, 97, 96, 87, 69, 66, 50]

來源

2011-05-03 16:10:08 deong

出於好奇，你是怎麼想出這個公式的？我不懷疑它是否有效，但對於我爲什麼它能正常工作並不是很明顯。 – 2011-05-03 16:19:01

我沒有。我的研究生顧問開發了一種算法，這個算法需要在幾年前完成（1989年是確切的，算法是一個稱爲Genitor的GA）。我意識到相同的要求，並將代碼拉到該算法。 :) – deong 2011-05-03 16:25:15

按等級標準化，然後構建二叉樹。選擇一個隨機double並找到相應的值。

來源

2011-05-03 15:52:45 dave

我會嘗試使用正態隨機方法（random.uniform(0, 1)），但平方概率。

由於P{x}的範圍是0 -> 1，P {x^2} also ranges from 0 - > 1`。

但重量是不均勻的，作爲平方少數還小，和平方更大數量變小。

只是一個想法。

來源

2011-05-03 16:00:49 Blender

這是一個好主意......事實上，任何函數x^y的工作範圍從0到1，因爲對於所有y，0^y = 0和1^y = 1。 – 2011-05-03 16:06:03

你有很多選擇;） – Blender 2011-05-03 16:07:48

我想你真正想要的是功能˚F：1，ñ]→ñ（自然數0，1，2，...）。這將爲每個等級分配一個權重。那麼你想挑選排名k的概率爲f（* k *）/（Σf（* i *）），換句話說，就是所有排名的權重之和的排名權重。要做到這一點，你可以簡單地在整個區間[1，Σ（* i *）]隨機抽取一個整數，根據你的位置計算出你的排名;如果你是在1 ... ˚F（1），挑1，如果你是在˚F（1）+1 ... ˚F（1）+ ˚F（2），挑2，等等。對於˚F其權重小的程度比大級別更高

一個可能的選擇是˚F（* I *）= ñ - 我 + 1，還有許多其他可能的選擇。

來源

2011-05-03 16:10:52

從區間1..n（K> 1）中生成K個隨機數並選擇最小值！

這有你想要的屬性，檢查了分佈的示範在http://www.sjsu.edu/faculty/watkins/samplemin.htm

爲了與K（1 <ķ< 2）的分數值這個工作，你可以做這樣的：

int m = random_int(1..n) 
if (random_double(0..1) <= K - 1): 
    m = min(m, random_int(1..n))

所以當K從上方接近1時，分佈變得越來越平坦。

來源

2011-05-03 17:20:44

不是一個壞建議，但我認爲K = 2的曲線甚至可能對我的需求來說太陡。 – 2011-05-03 17:26:13

好吧，添加一個解釋如何爲小數值1 2011-05-03 17:34:35

當然！非常好，謝謝。 – 2011-05-03 17:39:54

隨機選擇，按職級

回答

相關問題