1

给定一个从0开始的n个连续数的整数数组，即

0,1,2,..n

我希望n/2随机选择数字。

说n=5 那么一个可能的集合是0,3,5。

如何轻松实现？

4

6 回答 6

3

您可以遍历数字并确定每个数字应该出现在结果中的概率：

int n = 5;
int left = (n + 1) / 2;
int[] result = new int[left];
Random rnd = new Random();

for (int i = 0; left > 0; i++) {
  if (rnd.Next(n + 1 - i) < left) {
    result[result.Length - left] = i;
    left--;
  }
}

注意：这将始终产生排​​序结果。

编辑：

这是一个创建 200000000 个结果的测试运行，计算生成的组合（其中二进制数表示组合，例如 100110 是 0、3、4）：

010011 : 9999164
110001 : 10003346
010101 : 9990975
100101 : 9998154
101001 : 10006305
100110 : 10003350
101010 : 10000583
101100 : 9995335
011001 : 10000007
001011 : 10001492
001110 : 10001158
100011 : 9994680
110100 : 9998226
110010 : 9999954
011010 : 10002269
000111 : 10004752
010110 : 9996886
011100 : 9999196
111000 : 10001094
001101 : 10003074
于 2013-01-26T09:19:58.157 回答
2

我发现这样做的最简单方法是不完整的Fisher-Yates shuffle。在 n/2 次迭代后停止。

洗牌实际上适用于两个数组，即随机选择的数字和尚未使用的数字池，因此可供选择。碰巧这两个数组的总大小是原始数组长度，因此可以通过分区将它们存储在适当的位置。

在 n/2 次迭代之后，表示已选择数字的分区是从原始数组中随机选择的。

另一种看待这一点的方式是，完全洗牌结果的前 n/2 个数字不会被 n/2+1 次或洗牌的后续迭代所改变。

于 2013-01-26T09:09:33.177 回答
2

使用Fisher-Yates Shuffle，然后选择n/2数组中的第一个项目。

正如@Patricia Shanahan 在她的回答中指出的那样，只需要n/2使用 Fisher-Yates 对数组中的第一个项目进行洗牌。

于 2013-01-26T09:10:14.923 回答
0

一种有效地使用二进制属性对选择进行编码的方法是：

  1. 生成一个随机的 32 位无符号整数。

  2. 这样做 n/32 次，并将它们放入一个名为 mask 的数组中

  3. 这些随机整数的位选择所选数字。具体来说，如果单词大小为 32，那么如果 (masks[i/32] >> (i%32)) && 1 为真，则将选择 i。

由于随机 32 位整数平均有 16 个 0 和 16 个 1，因此此方法将接近您的 n/2 值。

假设你得到的 1 的实际数量是 W 并且与 n/2 相差 k，k = W - n/2

如果您选择的数字太少，则生成一个 0 到 n 范围内的随机整数，转到由该数字索引的那个位，并将遇到的第一个 0 更改为 1，向前搜索。

这样做k次。

在 k 太多的情况下，将遇到的第一个 1 更改为零。

这样做的好处是它也是存储子集的最紧凑的结构，每个位选择一个整数。你只需要范围，这个掩码数组，你就有你的选择。

此外，您生成的随机数必须比其他 shuffle 方法少 16 倍，从而提高效率。

最后，这种效率的提高随着字的大小而增加。对于 64 位无符号长整数，您获得的随机数比“n/2 交换排列方法”所需的随机数少 32 倍

祝你好运！

于 2013-01-26T09:16:55.143 回答
0

一种方法是使用带有 Next 的 Random 对象来生成向量编号的索引。您将新的生成值添加到 ArrayList 或 HashSet 之类的结构中以记住它。对于每次新生成的索引，您都要验证该结构中是否存在该值。

于 2013-01-26T09:13:03.013 回答
0

写的时候不允许Linqalgorithm吗？

int[] arrInts = new int[] {0, 1, 2, 3, 4, 5, 6};
var r = new Random();
var randomInts = arrInts.OrderBy(i => r.Next(arrInts.Length))
                        .Take(arrInts.Length/2)
                        .ToArray();

编辑：我不是 100% 确定性能，但使用.AsParallel()before可能会更好.OrderBy()。

我喜欢使用 Linq，因为它非常易读，而且我花了大约 5 秒来编写算法，而不是用几分钟来编写“手动”排序和循环。

于 2013-01-26T22:55:57.963 回答