2012-06-28 99 views
1

我希望從數組中隨機選擇元素,其中每個元素都有特定的被選擇概率。有沒有一種有效的方式來做到這一點,或者可能是Java已經完成的內容?從數組中隨機選擇一個元素,每個元素具有特定的概率

+1

沒有內置到我知道的Java語言中。你可能想看看apache-commons-math(http://commons.apache.org/math/),它有許多有用的工具類來做隨機化。此外,你可能會得到更好的答案,這個問題是你向人們展示了一些你試過寫過的代碼來解決問題,或者至少是一個通用的算法,以表明你已經試圖自己弄清楚。人們通常不會在你要求我們爲你工作的情況下欣賞問題。 ;) –

+0

嗯,我想到了一些天真的實現,似乎相當平凡但昂貴的使用,抱歉沒有包括我的代碼!感謝您的幫助,非常感謝:) – xlnc

回答

1

的一種方式是使用加權的概率這樣的:

MyClass getRandomElement(MyClass[] elements) 
{ 
    int totalWeight = 0; 
    for (MyClass element : elements) 
    { 
     totalWeight += element.weight; 
    } 

    int position = new Random().nextInt(totalWeight); 

    for (MyClass element : elements) 
    { 
     if (position < element.weight) 
     { 
      return element; 
     } 
     position -= element.weight; 
    } 
    throw new IllegalStateException("Should never get here"); 
} 
+0

這似乎是最好的方式來完成我所需要的,非常感謝你:) – xlnc

1

做到這一點的一種方法是建立一個數組,其中重複必要條款來表示它們的概率。因此,如果陣列中的項目A的概率爲.3,項目B的概率爲.7,則可以將它們放入10個項目的陣列中,A重複3次,B重複7.

然後,您可以使用隨機數生成器從數組中選擇一個索引。

另一種解決方案是將每個項目及其概率加載到數據結構中,將每個概率表示爲一個範圍(即項目A可以表示範圍0.5-8),然後生成隨機值從0-1開始,並抓取隨機數落入的任何範圍的值。

1

如果編碼在一個陣列中選擇的元件(可能是通過在陣列中的對象的成員變量)的概率重量你可以做如下:

  1. 假設你有重量爲整數的元素。
  2. 總和所有元素的權重。
  3. 在1和該權重之間創建一個隨機值。
  4. 遍歷數組,計數直到匹配隨機值。

實施例:

[1,3,2,5,2] 薩姆= 13 隨機軋輥= 5

元件[0] ..(我們已經計數,以1)

元件[1] ..(我們已經計數到4)

元件[2] ..(我們已經計數以6) 6> 5因此,我們選擇2.

現在,這需要O(n)時間,其中n是數組中值的數量。爲了提高效率,更好的方法是將值放在值所指示的位置。這有點像:

[a,b,b,b,c,c,d,d,d,d,d,e,e]。

查看counting sort瞭解更多詳情;它允許O(1)訪問。

2

的O(的log(n))的方法(這是直接從answer to a very similar question撕開):

通常的技術是將陣列轉化爲累加和的數組:

[10 60 5 25] --> [10 70 75 100] 

皮克從0到累計總數範圍內的隨機數(例如:0 <= x < 100)。然後,使用bisection累積陣列上的索引定位成原始陣列:

Random variable x  Index in the Cumulative Array  Value in Original Array 
-----------------  -----------------------------  ---------------------- 
0 <= x < 10      0       10 
10 <= x < 70      1       60 
70 <= x < 75      2        5 
75 <= x < 100      3       25 

例如,如果隨機變量X是4,二等分的累積陣列給出了對應於0的位置索引10在原始數組中。

而且,如果隨機變量x是72,那麼平分累積數組給出的位置索引爲2,其對應於原始數組中的5。

相關問題