以均勻隨機的方式選擇子集？

的問題是：以均勻隨機的方式選擇子集？

寫的方法隨機地從大小爲n的陣列產生一組M的整數。每個元素必須具有相同的被選擇概率。

這是正確的答案？：

我挑了第一個整數均勻隨機地。接下來選擇。如果它已經存在。我不會接受它。並繼續，直到我有整數。

來源

2011-06-06 xyz

只是感到這個過程可能不會終止，我們想要一個解決方案，這絕對是在理論上終止。這是正確的嗎？ – xyz 2011-06-06 11:58:46

你的意思是每個子集有相同的被選擇概率？ – 2011-06-06 12:04:49

它總是會終止，儘管取決於m和n的大小，可能不是非常有效。 – Rob 2011-06-07 20:47:49

 
let m be the number of elements to select 
for i = 1; i <= m; i++ 
    pick a random number from 1 to n, call it j 
    swap array[j] and array [n] (assuming 1 indexed arrays) 
    n--

在循環結束時，數組的最後m個元素是您的隨機子集。 Fisher-yates shuffle有一個變化。

來源

2011-06-06 19:15:08 frankc

+1（從前一陣子）我不認爲你已經正確地編寫了僞代碼，但反覆交換剛纔選擇的元素和矢量中最後一個未選定元素的一般想法是聲音...這樣你*維護*選擇和未選定的元素之間的劃分，並且可以每次使用一個隨機數來可靠地索引到尚未選定的元素...... – 2011-06-07 07:36:29

當我重新檢查代碼時，有一分鐘。這是可能的我犯了一個錯誤，但是，這是總體想法 – frankc 2011-06-07 14:26:31

我認爲這是正確的，但如果你看到一個錯誤，隨時編輯答案 – frankc 2011-06-07 17:37:14

有2^n個子集。選擇一個介於0和2^n-1之間的數字並將其轉換爲二進制。那些有位設置的應該從數組中取出並存儲。

例如考慮1,2,3,4集。

int[] a = new int[]{ 1, 2, 3, 4 } 
int n = (2*2*2*2) - 1; // 2^n -1 
int items = new Random().nextInt(n); 

// If items is 3 then this is 000011 so we would select 1 and 2 
// If items is 5 then this is 000101 so we would select 1 and 3 
// And so on 
for (int i=0;i<a.length;++i) { 
    if ((items & (1 << i)) != 0) { 
     // The bit is set, grab this item 
     System.out.println("Selected " + a[i]); 
    } 
}

來源

2011-06-06 11:57:28

但是你不想要一個隨機子集...你想要那裏有m個元素被選中......？ – 2011-06-07 05:24:47

想想你的原始範圍作爲從1-n列表中選擇，當你選擇一個元素（數字）從列表中刪除該元素。根據列表索引選擇元素，而不是實際的數字值。

int Choose1(List<int> elts) 
{ 
    var idx = rnd.Next(0,elts.Count); 
    var elt = elts[idx]; 
    elts.RemoveAt(idx); 
    return elt; 
} 

public List<int> Choose(int fromN, int chooseM) 
{ 
    var range = new List<int>(); 
    for (int i = 1; i <= fromN; i++) 
    { 
     range.Add(i); 
    } 
    var choices = new List<int>(); 
    for (int i = 0; i < chooseM; i++) 
    { 
     choices.Add(Choose1(range)); 
    } 
    return choices; 
}

使用列表將無法高效地爲大量涌現，但你可以使用相同的方法不實際構建任何列表，使用位運算。

來源

2011-06-07 20:58:37 Rob

在維基百科的幫助下，剛剛意識到這相當於由fisher-yates shuffle frankc – Rob 2011-06-08 09:33:31

如果您的選擇是隨機的，那麼按照您所描述的方式選取m項的概率將爲1/pow（n，m）。我認爲你需要的是1/C（n，m）。

來源

2012-09-08 23:18:47 abc

以均勻隨機的方式選擇子集？

回答

相關問題