c# - 从自然数中选择一个数字 < n 排除可能性

Question

给定 n 个自然数从 0 开始， b这是一个介于 0 到 n 之间的数字，我希望随机选择一个不包括 的数字b。

说 n 是 5 那么要选择的数字是{0,1,2,3,4,5} b 是 4，

那么我的随机选择来自{0,1,2,3,5}

一种方法是执行 while 循环，直到 random.nextInteger() 找不到 4。

除了使用 while 循环之外，还有什么容易做到的吗？

Answer 1

我会写一个简单的扩展：

// N.B. : min is inclusive, max is exclusive; so range is: [min,max) - {toExclude}
public static int Next(this Random rand, int min, int max, int toExclude)
{
    int v = rand.Next(min, max - 1);
    if (v < toExclude)
        return v;
    return v + 1;
}

用法：

var random = new Random();
var val = random.Next(0,6,4); // 6 because max is exclusive in C# random.Next()

Answer 2

如果您愿意，这是另一种方法：

import random

def random_unifrom(n,b):
    assert b < n and n > 0 and b > 0
    nMinusOneList = [i for i in range(n) if i != b]    
    lSize = len(nMinusOneList)
    randIndex = random.randint(0, lSize-1)
    return nMinusOneList[randIndex]

为了简单起见，我用python编写了这个。创建 nMinusOneList 的复杂度为 O(n)。返回随机索引复杂度取决于您使用的随机函数。

最后，如果您采用这种方法而不是 while 循环，您不会丢失任何东西，但即使您使用 while 循环方法，如果随机函数是随机的 (!!)，那么您应该没有问题。但是，我上面的方法从一开始就排除了您不需要的数字。

在 C# 中，我在 python 中使用的一行可能是几行，其中包含一个范围为 0 到 n 的 for 循环，条件是 x（for 循环索引）不等于 b，在构建列表时，然后您将获得排除 b 的列表。

Answer 3

在我的选择中，您的方法是最好的。它简单而优雅，即使m=2它是O(1)平均的（预期的重绘次数是1/2 + 1/4 + 1/8 + .... < 1）。

如果你想避免无限循环的最坏情况，还有另一种选择，尽管我怀疑它会对性能产生真正的影响。

1. 在 [0,1] 范围内绘制一个随机双精度数。顺其自然d。如果d < b/m：在 [0,b) 范围内绘制一个数字并返回它。
2. Else ( d > b/m) - 在范围内绘制一个随机数[b+1,m]并返回它。

请注意，它确实是均匀分布的，因为： range
中有m+1数字0,...,m，但只有m“有效”数字（不包括b）。
范围内有b数字0,1,...,b-1- 所以假设均匀分布，数字在这个范围内的概率是b/m- 正是P(d < b/m)。

在 java 中，它看起来类似于：

int m = 5, b = 4;
Random r = new Random();
double d = r.nextDouble();
if (d < ((double)b)/m) {
    System.out.println(r.nextInt(b));
} else { 
    System.out.println(r.nextInt(m-b) + b + 1);
}