问题提供了所有必要的数据: 如何在给定区间 [0,N-1] 内生成一个由K个非重复整数组成的有效算法。如果 K 很大并且接近于 N，那么朴素算法(生成随机数并在将其添加到序列之前查找它们是否已经存在)是非常昂贵的。
Efficiently selecting a set of random elements from a linked list 提供的算法似乎比必要的复杂，并且需要一些实现。我刚刚找到了另一种算法，只需在单次遍历中知道所有相关参数即可完成工作。
如何高效地生成一个介于0和上限N之间、包含K个不重复整数的列表？
29
- tucuxi
4
等等，如果你已经找到了另一个算法，那问题是什么？ - Dark Shikari
1这个算法真是太棒了！不得不和别人分享一下 - 根据 http://stackoverflow.com/faq 的建议，这似乎是推荐的行为：“提出并回答自己的编程问题也完全没问题，但要假装你在参加Jeopardy节目。” - tucuxi
1对我来说，这个答案看起来最好。 - Fakrudeen
@tucuxi 我得到了在 http://meta.stackoverflow.com/questions/334325/a-few-intersecting-questions-about-picking-k-elements-of-n 上缩小范围的完全自由。不可否认，我应该在编辑摘要中提到这一点。 - ivan_pozdeev
13个回答
13
在计算机程序设计艺术 第二卷: 半数值算法 第三版中，Knuth描述了以下选择采样算法：
算法S（选择采样技术）。从一组N个记录中随机选择n个记录，其中0 < n ≤ N。 S1. [初始化] 设置t←0、m←0。（在此算法期间，m表示到目前为止选定的记录数量，t是我们已处理的输入记录总数。） S2. [生成U] 生成介于零和一之间均匀分布的随机数U。 S3. [检验] 如果（N - t）U ≥ n - m，则转到步骤S5。 S4. [选择] 选择样本中的下一个记录，并将m和t增加1。如果m这里是一个Common Lisp实现，可以更容易地理解该算法如何从列表中选择n个随机成员：
算法S（选择采样技术）。从一组N个记录中随机选择n个记录，其中0 < n ≤ N。 S1. [初始化] 设置t←0、m←0。（在此算法期间，m表示到目前为止选定的记录数量，t是我们已处理的输入记录总数。） S2. [生成U] 生成介于零和一之间均匀分布的随机数U。 S3. [检验] 如果（N - t）U ≥ n - m，则转到步骤S5。 S4. [选择] 选择样本中的下一个记录，并将m和t增加1。如果m这里是一个Common Lisp实现，可以更容易地理解该算法如何从列表中选择n个随机成员：
(defun sample-list (n list &optional (length (length list)) result)
(cond ((= length 0) result)
((< (* length (random 1.0)) n)
(sample-list (1- n) (cdr list) (1- length)
(cons (car list) result)))
(t (sample-list n (cdr list) (1- length) result))))
这里有一种不使用递归且适用于所有类型序列的实现：
(defun sample (n sequence)
(let ((length (length sequence))
(result (subseq sequence 0 n)))
(loop
with m = 0
for i from 0 and u = (random 1.0)
do (when (< (* (- length i) u)
(- n m))
(setf (elt result m) (elt sequence i))
(incf m))
until (= m n))
result))
- Vebjorn Ljosa
1
1非常感谢您权威的回答。我有同样的需求，而且这正是我计划实现的算法。再次感谢。 - Sundar R
12
Python库中的random模块使其变得异常易用和高效：
from random import sample
print sample(xrange(N), K)
sample函数从给定序列中返回一个包含K个独特元素的列表。
xrange是一个“列表仿真器”，它的行为类似于连续数字的列表，但是不会在内存中创建它，这使得类似于这样的任务超级快速。
- DzinX
5
6Python的实现相当不错（请参阅http://svn.python.org/view/python/trunk/Lib/random.py?view=markup，搜索“sample”）。他们区分了两种情况，一种是大K（接近N），另一种是小K。对于大K，它们有选择地复制元素。对于小K，它们随机抽取元素，使用set来避免重复。 - tucuxi
3对于大序列来说，这种方法在内存方面效率较低。 - Jonathan Hartley
https://hg.python.org/cpython/file/tip/Lib/random.py 是新的源代码链接。 - ivan_pozdeev
为什么不直接使用
random.shuffle？ - Tobias Kienzler答案缺乏解释 - 请参考Jonathan Hartley的评论。 - Imago
5
- Arachnid
5
不错的文章。但是，“XOR折叠”不会破坏唯一性吗？当然，x！= y意味着encipher（x）！= encipher（y）以使解码工作，但是使用例如（encipher（x）>> 4）^（encipher（x）& MASK）可能会将不同的x值“折叠”到相同的代码中-因此您的“排列”可能包含重复项。 - j_random_hacker
我手头没有理论基础，但是不，它不会破坏分组密码的一对一映射特性。Xor折叠是从TEA加密中借鉴的——也许可以参考相关文献以获取更多细节。 - Nick Johnson
@j_random_hacker：当然，你是对的。但是仍然可以使用自定义Feistel密码来生成伪随机置换，使用某些加密哈希函数作为函数F。 - sellibitze
请看这里：https://dev59.com/3nVC5IYBdhLWcg3wvT7g#3094476 - sellibitze
对于今天阅读此内容的任何人而言，虽然这种方法听起来可能更好，但是在我的实验中，使用
random中的sample方法与range一起使用，即使只使用单个周期，速度也比TEA更快。此外，当仅使用v0作为输出时，我偶尔会得到重复项。对于该实验，我创建了一个基于TEA的数字生成器，并初始化和计算了10,000组2048个数字，并出现了6个生成重复项的情况。也许多个周期会有所帮助，但即使对于一个周期，它已经比random.sample慢了，后者还保证了唯一的数字。 - Stefan Fabian3
以下代码（使用 C 语言编写，出处不明）似乎非常有效的解决了该问题：
/* generate N sorted, non-duplicate integers in [0, max] */
int *generate(int n, int max) {
int i, m, a;
int *g = (int *)calloc(n, sizeof(int));
if (!g) return 0;
m = 0;
for (i = 0; i < max; i++) {
a = random_in_between(0, max - i);
if (a < n - m) {
g[m] = i;
m++;
}
}
return g;
}
有没有人知道我能在哪里找到更多像这样的宝石？
- tucuxi
7
3《Programming Pearls》是Jon Bentley的著作（"gems"这个双关语是有意而为之）。 - Bill the Lizard
"random_in_between" 是什么意思？ - Luis Filipe
2这个算法对于从大集合中选择的小样本非常低效。从一百万个整数中选择5个需要调用rand()函数一百万次，而不是5次。 - Rafał Dowgird
感谢书名 - 我想不到其他找到它的方法了。Luis，random_in_between是用于“在lo和hi之间的数字，不包括hi”。Praptak，完全正确。应该指定“内存效率”与“时间效率”。至少保证在有限的时间内完成... - tucuxi
请注意，此答案返回一个已排序的列表，这不是最初问题的要求。 - cmcginty
显示剩余2条评论
2
生成一个数组
然后随机打乱前
洗牌：
这本质上是从列表中随机选择一个元素，将其移出，然后从剩余列表中随机选择一个元素，以此类推。
时间复杂度为O(K)和O(N)，需要O(N)的存储空间。
洗牌部分称为Fisher-Yates shuffle或Knuth's shuffle，在《计算机程序设计艺术》第2卷中有描述。
0...N-1，并填充a[i]=i。然后随机打乱前
K项。洗牌：
- 开始时
J=N-1 - 选取一个随机数
0...J（比如R） - 交换
a[R]和a[J]- 由于
R可能等于J，因此元素可能与自身交换
- 由于
- 从
J中减去1并重复。
K个最后元素。这本质上是从列表中随机选择一个元素，将其移出，然后从剩余列表中随机选择一个元素，以此类推。
时间复杂度为O(K)和O(N)，需要O(N)的存储空间。
洗牌部分称为Fisher-Yates shuffle或Knuth's shuffle，在《计算机程序设计艺术》第2卷中有描述。
- James Curran
8
你的方法可以生成 [0, N[ 范围内的排列，但我需要在 [0, K[ 范围内生成数字。例如，如果 N=2 且 K=10，则 {5, 9} 是一个有效的输出序列。 - tucuxi
然后生成0到K之间的数字，再随机删除数字，直到你得到N个数字。 - Dark Shikari
@ivan_pozdeev 不是的。请注意，在我的例子中，R首先在范围0...9内，这意味着R可能等于9，并且A [9]与自身交换。 - James Curran
我进行了30M次测试，差异大约为0.001%左右。 - ivan_pozdeev
显示剩余3条评论
1
步骤1：生成整数列表。
步骤2：执行Knuth Shuffle。
请注意，您不需要对整个列表进行洗牌，因为Knuth Shuffle算法允许您仅应用n次洗牌，其中n是要返回的元素数量。生成列表仍将花费与列表大小成比例的时间，但您可以重复使用现有列表以满足任何未来的洗牌需求（假设大小保持不变），而无需在重新启动洗牌算法之前预先洗牌部分洗牌列表。
Knuth Shuffle的基本算法是从整数列表开始。然后，您将第一个整数与列表中的任何数字交换，并返回当前（新）第一个整数。然后，您将第二个整数与列表中的任何数字（除第一个数字外）交换，并返回当前（新）第二个整数。然后...等等...
这是一个非常简单的算法，但请注意，在执行交换时，请确保包括列表中的当前项目，否则您将破坏该算法。
- Brian
1
通过将K个数字存储在哈希存储中，加速微不足道的算法。在开始之前知道K可以消除插入哈希映射的所有低效率，并且仍然可以获得快速查找的好处。
- Bill the Lizard
4
1是的，当我需要一千万个不重复的随机数用于彩票时，我就是这样做的。 - axk
不太节省内存 - 需要一个大小为K的辅助结构。在时间上，您需要进行K次插入和N次删除。我找到的算法只需要（最多）K个随机抽样。 - tucuxi
你根本不需要辅助结构。只需将映射作为唯一的结构即可。存储K个项目始终需要K次插入。为什么需要N次删除呢？ - Bill the Lizard
把数据插入到大小为K的数据结构中，以及检查其中是否存在并不是简单算法的问题所在。问题在于随着K -> N，当填充序列末尾时，您的RNG生成已经出现过的数字的概率非常高。您需要一个哈希映射，但这只是辅助的。 - Greg Rogers
1
我的解决方案是以C++为导向的，但我相信它可以翻译成其他语言，因为它非常简单。
- 首先，生成一个从0到K的K个元素的链表
- 然后只要列表不为空，就生成一个介于0和向量大小之间的随机数
- 将该元素取出，推入另一个向量中，并从原始列表中删除它
这个解决方案只涉及两个循环迭代，没有哈希表查找或任何类似的东西。所以在实际代码中：
// Assume K is the highest number in the list
std::vector<int> sorted_list;
std::vector<int> random_list;
for(int i = 0; i < K; ++i) {
sorted_list.push_back(i);
}
// Loop to K - 1 elements, as this will cause problems when trying to erase
// the first element
while(!sorted_list.size() > 1) {
int rand_index = rand() % sorted_list.size();
random_list.push_back(sorted_list.at(rand_index));
sorted_list.erase(sorted_list.begin() + rand_index);
}
// Finally push back the last remaining element to the random list
// The if() statement here is just a sanity check, in case K == 0
if(!sorted_list.empty()) {
random_list.push_back(sorted_list.at(0));
}
- sqook
0
如果列表已排序，例如，如果您想从N个元素中提取K个元素，但不关心它们的相对顺序，则论文An Efficient Algorithm for Sequential Random Sampling（Jeffrey Scott Vitter，《ACM Transactions on Mathematical Software》，Vol. 13，No. 1，March 1987，Pages 56-67.）中提出了一种有效的算法。
编辑以添加使用boost的c++代码。我刚刚输入了它，可能会有很多错误。随机数来自boost库，使用愚蠢的种子，因此请勿在此基础上进行任何严肃的操作。
/* Sampling according to [Vitter87].
*
* Bibliography
* [Vitter 87]
* Jeffrey Scott Vitter,
* An Efficient Algorithm for Sequential Random Sampling
* ACM Transactions on MAthematical Software, 13 (1), 58 (1987).
*/
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <boost/random/linear_congruential.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/uniform_real.hpp>
using namespace std;
// This is a typedef for a random number generator.
// Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand
typedef boost::minstd_rand base_generator_type;
// Define a random number generator and initialize it with a reproducible
// seed.
// (The seed is unsigned, otherwise the wrong overload may be selected
// when using mt19937 as the base_generator_type.)
base_generator_type generator(0xBB84u);
//TODO : change the seed above !
// Defines the suitable uniform ditribution.
boost::uniform_real<> uni_dist(0,1);
boost::variate_generator<base_generator_type&, boost::uniform_real<> > uni(generator, uni_dist);
void SequentialSamplesMethodA(int K, int N)
// Outputs K sorted random integers out of 0..N, taken according to
// [Vitter87], method A.
{
int top=N-K, S, curr=0, currsample=-1;
double Nreal=N, quot=1., V;
while (K>=2)
{
V=uni();
S=0;
quot=top/Nreal;
while (quot > V)
{
S++; top--; Nreal--;
quot *= top/Nreal;
}
currsample+=1+S;
cout << curr << " : " << currsample << "\n";
Nreal--; K--;curr++;
}
// special case K=1 to avoid overflow
S=floor(round(Nreal)*uni());
currsample+=1+S;
cout << curr << " : " << currsample << "\n";
}
void SequentialSamplesMethodD(int K, int N)
// Outputs K sorted random integers out of 0..N, taken according to
// [Vitter87], method D.
{
const int negalphainv=-13; //between -20 and -7 according to [Vitter87]
//optimized for an implementation in 1987 !!!
int curr=0, currsample=0;
int threshold=-negalphainv*K;
double Kreal=K, Kinv=1./Kreal, Nreal=N;
double Vprime=exp(log(uni())*Kinv);
int qu1=N+1-K; double qu1real=qu1;
double Kmin1inv, X, U, negSreal, y1, y2, top, bottom;
int S, limit;
while ((K>1)&&(threshold<N))
{
Kmin1inv=1./(Kreal-1.);
while(1)
{//Step D2: generate X and U
while(1)
{
X=Nreal*(1-Vprime);
S=floor(X);
if (S<qu1) {break;}
Vprime=exp(log(uni())*Kinv);
}
U=uni();
negSreal=-S;
//step D3: Accept ?
y1=exp(log(U*Nreal/qu1real)*Kmin1inv);
Vprime=y1*(1. - X/Nreal)*(qu1real/(negSreal+qu1real));
if (Vprime <=1.) {break;} //Accept ! Test [Vitter87](2.8) is true
//step D4 Accept ?
y2=0; top=Nreal-1.;
if (K-1 > S)
{bottom=Nreal-Kreal; limit=N-S;}
else {bottom=Nreal+negSreal-1.; limit=qu1;}
for(int t=N-1;t>=limit;t--)
{y2*=top/bottom;top--; bottom--;}
if (Nreal/(Nreal-X)>=y1*exp(log(y2)*Kmin1inv))
{//Accept !
Vprime=exp(log(uni())*Kmin1inv);
break;
}
Vprime=exp(log(uni())*Kmin1inv);
}
// Step D5: Select the (S+1)th record
currsample+=1+S;
cout << curr << " : " << currsample << "\n";
curr++;
N-=S+1; Nreal+=negSreal-1.;
K-=1; Kreal-=1; Kinv=Kmin1inv;
qu1-=S; qu1real+=negSreal;
threshold+=negalphainv;
}
if (K>1) {SequentialSamplesMethodA(K, N);}
else {
S=floor(N*Vprime);
currsample+=1+S;
cout << curr << " : " << currsample << "\n";
}
}
int main(void)
{
int Ntest=10000000, Ktest=Ntest/100;
SequentialSamplesMethodD(Ktest,Ntest);
return 0;
}
$ time ./sampling|tail
在我的笔记本上输出如下
99990 : 9998882
99991 : 9998885
99992 : 9999021
99993 : 9999058
99994 : 9999339
99995 : 9999359
99996 : 9999411
99997 : 9999427
99998 : 9999584
99999 : 9999745
real 0m0.075s
user 0m0.060s
sys 0m0.000s
- Frédéric Grosshans
2
根据 https://dev59.com/W3E95IYBdhLWcg3wPrgI#2394292 ，这会生成组合，而不是排列。 - ivan_pozdeev
被要求的是“K个不重复整数的列表”，而不是排列。在我的答案中，我指定“如果您不关心顺序”。 - Frédéric Grosshans
0
蓄水池抽样版本非常简单：
my $N = 20;
my $k;
my @r;
while(<>) {
if(++$k <= $N) {
push @r, $_;
} elsif(rand(1) <= ($N/$k)) {
$r[rand(@r)] = $_;
}
}
print @r;
这是从标准输入中随机选择的 $N 行。如果您不使用文件中的行，则将 <>/$_ 替换为其他内容，但这是一个非常简单的算法。
- Michael Cramer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接