C ++ 11 Randomly between int x, int y, excluding list <int>
I need a way to generate random integers between x, y, but once a random z is generated, I need the next iteration of x, y to eliminate z (or better yet, an ints exception list). The return value must match the "std :: uniform_int_distribution <>" condition. There is an obvious way to do this, but I was hoping for a quick version.
int GenerateRandomBetweenExcluding(int min, int max, int exclude) // even better is a list<int> to exclude
{
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(min, max); // how to exclude "exclude" or list<int>?
int randNum = dis(gen);
return randNum;
}
source to share
#include <algorithm>
#include <vector>
#include <random>
class NoRepeat
{
public:
void Init(int,int);
int GetOne();
bool HasMore();
private:
std::vector<int> list;
};
void NoRepeat::Init(int min, int max) // min and max are inclusive
{
list.clear();
list.reserve(max-min+1);
for( int i=min; i<=max; ++i )
list.push_back(i);
std::random_shuffle( list.begin(), list.end() );
// might want to supply own random_func, default uses rand()
}
bool NoRepeat::HasMore()
{
return !list.empty();
}
int NoRepeat::GetOne()
{
int ret = list.back();
list.pop_back();
return ret;
}
source to share
A good way to do this is if the list of exceptions is sorted in ascending order. You can achieve this sort by using set<int>
instead list<int>
to track exceptions; most installation operations take log(n)
time, and it is guaranteed that the container will be sorted at any time.
The algorithm looks like this:
set<int> exclude;
/* ... configure generator and exclusion set ... */
uniform_int_distribution<> dis(min, max-exclude.size());
int val = dis(gen);
/* skip over the exclusions */
for(int i : exclude) {
if(val >= i) val++;
else break;
}
return val;
source to share