我需要从一个包含N个记录的集合中随机选择n条记录（其中0 < n < N）。
一种可能的算法是：
遍历列表，对于每个元素，使其被选中的概率等于
(所需数量) / (剩余数量)因此，如果你有40个项目，则第一个项目被选中的概率为
5/40。如果它被选中，则下一个项目的概率为
4/39，否则为5/39。当你到达最后一个元素时，你将得到你的5个项目，而通常在那之前就已经得到所有项目了。
假设有一个良好的伪随机数生成器，这个算法是否正确？
注意
在stackoverflow上有很多这种问题（其中很多被标记为C#中从List<T>中选择N个随机元素的重复问题）。
上述算法经常被提出（例如Kyle Cronin的答案），但总是受到质疑（例如，请参见这里，这里，这里，这里…）。
我可以就此事发表最后的看法吗？
这个算法是绝对正确的。
它不是一个突然想出来的好方法，而是一种被称为选择取样/算法S（由Fan、Muller和Rezucha（1）在1962年发现，独立于Jones（2）），在TAOCP-第2卷-半数值算法-§3.4.2中有很好的描述。
正如Knuth所说：
乍一看，这个算法可能不可靠，甚至是错误的。但仔细分析后可以发现它是完全可信的。
该算法从大小为N的集合中抽取n个元素，当已经选出m个元素时，第t+1个元素以(n-m)/(N-t)的概率被选中。
n / N），则第二个元素被选中的概率为 (n - 1) / (N - 1)；如果没有选择第一个元素，则第二个元素被选中的概率为 n / (N - 1)。选择第二个元素的总体概率为 (n / N) ((n - 1) / (N - 1)) + (1 - n/N)(n / (N - 1)) = n/N。
TAOCP - Vol 2 - Section 3.4.2 exercise 3
除了理论考虑，算法S（以及算法R / 蓄水池抽样）被许多知名库使用（例如SGI的原始STL实现, std::experimental::sample, random.sample在Python中...）。O(N)（即使我们通常不必遍历所有N条记录：当n=2时，考虑的平均记录数约为2/3 N；一般公式见TAOCP - Vol 2 - § 3.4.2 - ex 5/6）;N的值事先未知时，无法使用。无论如何，它都能工作！
编辑
你如何以7/22的概率随机选择此项？
[删减]
在罕见情况下，您可能会在想要5个元素时选择4或6个元素
这来自N3925（进行了小修改以避免常见的接口/标记分派）：
template<class PopIter, class SampleIter, class Size, class URNG>
SampleIter sample(PopIter first, PopIter last, SampleIter out, Size n, URNG &&g)
{
using dist_t = uniform_int_distribution<Size>;
using param_t = typename dist_t::param_type;
dist_t d{};
Size unsampled_sz = distance(first, last);
for (n = min(n, unsampled_sz); n != 0; ++first)
{
param_t const p{0, --unsampled_sz};
if (d(g, p) < n) { *out++ = *first; --n; }
}
return out;
}
没有浮点数。
uniform_int_distribution“如广告所述”运作正常，则没有偏差。sample()方法或函数如何以7/22的概率返回true/false。 - Edward Ned HarveyPopIter）来访问输入集合，但只需要输出迭代器（PopIter）来生成结果样本。这是一个C++技术细节，并不是普遍感兴趣的问题，但我不想太过改动原始源代码。你在其他评论中已经强调了关键点：d(g, p)类似于UInt32 RandomRange()。不管怎样，我也看到很多答案受到你描述的这个问题的影响（例如https://dev59.com/TGw15IYBdhLWcg3wo9Vx#6482925）。 - manlio bool RandomSelect(int x, int y) 方法，或者只是RS(x,y) 方法，旨在以 x/y 的概率返回 true。如果您不太关心准确性，通常给出的答案是使用return Random.NextDouble() < (double)x/(double)y;，这是不精确的，因为Random.NextDouble() 不精确且不完全均匀，并且除法(double)x/(double)y 也不精确。使用< 或<= 应该无关紧要（但实际上不是），因为理论上不可能随机选择精确等于指定概率的无限精度随机数。虽然我确信可以创建或找到一种算法，以精确实现 RS(x,y) 方法，从而使您能够正确实现所描述的算法，但我认为简单地回答“是，算法是正确的”会误导人们进行使用 double 计算和选择元素而不知道引入的偏差。
请不要误解我的意思 - 我并不是说每个人都应该避免使用所描述的算法 - 我只是想说，除非你找到一种更精确的实现RS(x,y)算法的方法，否则你的选择将会在某些元素上比其他元素更加偏向。
如果你关心公平性（所有可能结果的等概率性），我认为最好、最容易理解的方法是使用另一种算法，如下所述：
如果你认为你唯一可用的随机源是随机位，那么你必须定义一种随机选择技术，以确保在给定二进制随机数据的情况下具有相等的概率。这意味着，如果你想从一个2的幂次方范围内选择一个随机数，你只需选择随机位并返回它们。但是，如果你想在不是2的幂次方的范围内选择一个随机数，你需要获取更多的随机位，并且丢弃不能映射到公平结果的结果（放弃随机数并重试）。我在这里用图示和C#示例代码进行了博客记录：https://nedharvey.com/blog/?p=284 从你的集合中重复随机选择，直到你有n个唯一的项目。
std::uniform_int_distribution <unsigned>]（http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution）作为随机数分布， unsigned用于n和N），因此它避免了浮点数固有的精度不足。 - manliostd::uniform_int_distribution<unsigned> 会在一个范围内产生随机整数，与我博客文章中的 UInt32 RandomRange() 相同。它不是 RS(x,y) 的实现。你的评论让我意识到我的回答并没有直接回答你的问题，所以我进行了修订。 - Edward Ned HarveyUInt32 RandomRange(UInt32 max) 函数，那么 bool RandomSelect(int x, int y) { return RandomRange(y-1) < x; } 怎么样？如果 RandomRange 提供了相等的分布，这应该不会像 double 实现一样存在问题。 - grek40random.py中在_randbelow函数内部实现的，所以你是错误的。 - Edward Ned Harvey