CODEWITHSUNDEEP
c++
codelover123
codelover123

Reputation: 187

How to randomly pick a element from a set in c++?

Given a set of integers:

std::set<int> itemInTest;

There are about 4000 integers in this set and I want to loop 100 times, each time it can pick 100 different elements from the set randomly. In addition, all the integers are positive.

how to randomly pick one of them each time? I know there are many answers in stackoverflow, but some are too complex and some are not so random.

Upvotes: 4

Views: 826

Answers (2)

John Zwinck
John Zwinck

Reputation: 249103

First, put your items into a vector since you will need to randomly access them many times:

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

Then, if you need 100 items and don't want to pick the same one twice, you may as well just shuffle the whole thing:

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

Now just take the first 100 elements. If you want them in a set again:

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

Or you can use any output container type you like--including vector.

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

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

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

Upvotes: 8

Jarod42
Jarod42

Reputation: 217085

You may use Fisher–Yates shuffle:

Something like:

// 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;
}

Live example

then from indexes, you take value from your set (which should be transformed into vector for random access).

Upvotes: 1

Related Questions