C++ 11 Случайно между int x, int y, за исключением списка <int>

Question

Мне нужен способ генерации случайных целых чисел между x, y, но как только генерируется случайный z, мне нужна следующая итерация x, y, чтобы исключить z (или, еще лучше, список ints для исключения). Возвращаемое значение должно соответствовать условию «std :: uniform_int_distribution <>». Существует очевидный способ сделать это, но я надеялся на быструю версию.

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

Answer 1

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

Answer 2

Используйте список со всеми номерами от min до max. Выберите случайным образом элемент и удалите его.

Answer 3

Есть хороший способ сделать это, если список исключений отсортирован в порядке возрастания. Вы можете добиться этой сортировки, используя set<int> вместо list<int> для отслеживания исключений; большинство заданных операций принимают log(n) времени, и контейнер гарантированно будет сортироваться в любое время.

Алгоритм выглядит следующим образом:

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;