以均匀随机的方式选择子集？

的问题是：以均匀随机的方式选择子集？

写的方法随机地从大小为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

以均匀随机的方式选择子集？

回答

相关问题