How to randomly select an element from a set in C ++?

Question

Given a lot of integers:

std::set<int> itemInTest; 

This set contains about 4,000 integers, and I want the loop to be 100 times, each time it can select 100 different elements from the set randomly. In addition, all integers are positive.

How to randomly choose one of them every time? I know there are many answers in stackoverflow, but some of them are too complicated, and some are not so random.

Answer 1

First, put your objects in a vector, as you will need random access to them many times:

 vector<int> items(itemInTest.begin(), itemInTest.end()); 

Then, if you need 100 items and you do not want to select the same thing twice, you can just shuffle all of this:

 std::random_device rd; std::mt19937 gr(rd()); shuffle(items.begin(), items.end(), gr); 

Now just grab the first 100 items. If you want them to be in the set again:

 set<int> result(items.begin(), items.begin() + 100); 

Or you can use any type of output type you choose - including a vector.

You can do the random_shuffle step again until you finish 100 iterations.

If you don't have C ++ 11, you can use std::random_shuffle() instead of std::shuffle() , noting that the quality of randomness can be reduced. Then you do not need std::mt19937 , just:

 random_shuffle(items.begin(), items.end()); 

Answer 2

You can use Fisher-Yates shuffle :

Sort of:

 // Fisher–Yates_shuffle std::vector<int> FisherYatesShuffle(std::size_t size, std::size_t max_size, std::mt19937& gen) { assert(size < max_size); std::vector<int> b(size); for(std::size_t i = 0; i != max_size; ++i) { std::uniform_int_distribution<> dis(0, i); std::size_t j = dis(gen); if(j < b.size()) { if(i < j) { b[i] = b[j]; } b[j] = i; } } return b; } 

Real time example

then from the indices you take the value from your set (which should be converted to vector for random access).