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

Question

问题是：

编写一个方法，从大小为 n 的数组中随机生成一组 m 个整数。每个 元素必须具有相同的被选择概率。

这个答案正确吗？：

我均匀随机地选择第一个整数。 选择下一个。如果它已经存在。我不接受，否则接受。继续直到我有 m 个整数。

Answer 1

如果您的选择是随机的，那么按照您描述的方式选择 m 个项目的概率将为 1/pow(n,m)。我认为你需要的是 1/C(n,m)。

Answer 2

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 洗牌有一种变体。

Answer 3

有 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]);
   }
}

Answer 4

将要选择的原始范围视为 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;
}

使用列表对于大量数据来说效率不高，但是您可以使用相同的方法，而无需实际构建任何列表，只需使用一些算术即可。