lundi 2 février 2015

C++ randomly sample k numbers from range 0:n-1 (n > k) without replacement

How do I best randomly sample k numbers from a range 0:n-1 (for n > k) without replacement in C++?


I've considered the following pseudocode (inspired by the third example on cppreference.com), but I feel like it's a bit hacky:



initialize vect<int> v of size n
for i = 0 to n-1
v[i] = i
shuffle v
return v[0 to k-1]


The drawback here is also the requirement to build a massive array first too. That seems like slow/clunky overkill.


I would love some direction here if you can help. I'm less interested in the theory (algorithms are interesting but not relevant to my needs now) than the best way to implement this in C++.


Thanks in advance!





Aucun commentaire:

Enregistrer un commentaire