首页 > 代码库 > reservoir sampling / random shuffle
reservoir sampling / random shuffle
randomly choose a sample of k items from a list S containing n elements, the algorithm may be online (i.e. the input list is unknown beforehand)
https://en.wikipedia.org/wiki/Reservoir_sampling
ReserviorSampling(Source[1..n], Result[1..k]) { for (int i = 1; i <= k; i++) { Result[i] = Source[i]; } for (int i = k+1; i <= n; i++) { int rand = Random.get(1, i); // both 1 and i are inclusive if (rand <= k) { Result[rand] = Source[i]; } } return Result;}
vector<int> shuffle(const vector<int> &nums) { auto ret = nums; int n = ret.size(); for (int i = 0; i < n; i++) { int s = rand()%(n-i)+i; swap(ret[i], ret[s]); } return ret; }
reservoir sampling / random shuffle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。