我的程序是编写一个c ++程序初始化一个大小为SIZE的整数向量v,其中每个区别在[0,2 * SIZE]范围内,我如何确保向量中的所有数字都是唯一的如何编辑我的初始化向量,使其正常工作,我的逻辑中的某些东西是有缺陷的。随机播放不能使用。
#include <iostream>
#include <ctime>
#include <vector>
#include <iomanip>
#include<algorithm>
const int SIZE =10;
unsigned int seed = (unsigned)time(0);
using namespace std;
double random (unsigned int &seed);
void print_vector (vector<int> :: iterator b,
vector<int> :: iterator e );
void initialize_vector(vector<int> &v);
vector<int>v;
int main()
{
cout << endl;
initialize_vector(v);
cout << "Vector : " << endl;
print_vector(v.begin(), v.end());
return 0;
}
double random(unsigned int &seed)
{
const int MODULUS = 15749;
const int MULTIPLIER = 69069;
const int INCREMENT = 1;
seed = ((MULTIPLIER*seed)+INCREMENT)%MODULUS;
return double (seed)/MODULUS;
}
void initialize_vector(vector<int> &v)
{
vector<int> used;
int count_unused, k;
for (int i=0; i<2*SIZE; i++)
{
used.push_back(0);
}
for (int i=0; i<SIZE; i++)
{
int j= (random(seed)*(2*SIZE+1-i)) + 1;
count_unused = 0;
k = 0;
while (count_unused != j)
{
if (used[k] == 0)
count_unused++;
k++;
}
used[k] = 1;
v.push_back(j);
}
}
void print_vector (vector<int> :: iterator b,
vector<int> :: iterator e )
{
vector<int> :: iterator p =b;
while(p<e)
cout << setw(3) << (*p++);
cout << endl;
}
std::iota
和std::random_shuffle
1诀窍:
constexpr int SIZE = 10;
std::vector<int> values(2*SIZE+1);
std::iota(begin(values), end(values), 0);
std::random_shuffle(begin(values), end(values));
values.resize(SIZE);
完整演示:http://coliru.stacked-crooked.com/a/0caca71a15fbd698
首先,创建2*SIZE+1
的向量...
std::vector<int> values(2*SIZE+1);
......并且填充了从0
到2*SIZE
的连续整数。
std::iota(begin(values), end(values), 0);
我们洗牌这些价值......
std::random_shuffle(begin(values), end(values));
...并删除第二个无用的一半。
values.resize(SIZE);
瞧。
1)注意:这是一个C ++ 11/14解决方案,因为std::random_shuffle
自C ++ 14以来已被弃用,并在c ++ 17中被删除。
好的,这是没有任何存储和基于Reservoir Sampling检查的解决方案。我们使用0到2 * SIZE的值来模拟流,并以相等的概率填充储层。无需预先填充然后擦除数据,一次采样。没有SHUFFLE!代码,Visual C ++ 2019
#include <iostream>
#include <vector>
#include <random>
constexpr int SIZE = 10;
constexpr int EOS = -1; // end-of-stream marker
static int s = 0;
void init_stream() {
s = 0;
}
int next_stream() {
if (s > 2 * SIZE)
return EOS;
return s++;
}
std::mt19937_64 rng{ 1792837ULL };
int random(int lo, int hi) {
std::uniform_int_distribution<int> ud{ lo, hi };
return ud(rng);
}
std::vector<int> reservoir(int size) {
std::vector<int> r(size, 0);
auto v = next_stream(); // value from stream
for (int k = 0; v != EOS; ++k, v = next_stream()) {
if (k < r.size()) { // fill reservoir
r[k] = v;
}
else { // replace elements with gradually decreasing probability
unsigned int idx = random(0, k);
if (idx < r.size()) {
r[idx] = v;
}
}
}
return r;
}
int main() {
std::vector<int> h(2*SIZE+1, 0);
for (int k = 0; k != 100000; ++k) {
init_stream();
std::vector<int> r{ reservoir(SIZE) };
for (auto v : r) {
h[v] += 1;
}
}
for (auto v : h) {
std::cout << v << '\n';
}
return 0;
}
打印的直方图显示非常均匀的分布。
As mentioned by sv90在没有shuffle
的情况下,或者在非常大的SIZE
s你可能更喜欢unordered_set
以确保唯一的数字。用unordered_set
初始化这个uniform_int_distribution
然后用这个vector
初始化你的unordered_set
。像这样的东西:
unordered_set<int> initialize_vector;
mt19937 g{ random_device{}() };
const uniform_int_distribution<int> random{ 0, SIZE };
while(size(initialize_vector) < SIZE) {
initialize_vector.insert(random(g));
}
const vector<int> v{ cbegin(initialize_vector), cend(initialize_vector) };