C++ случайный выбор k чисел из диапазона 0: n-1 (n> k) без замены

Question

Я работаю над переносом моделирования MATLAB на C++. Для этого я пытаюсь воспроизвести MATLAB's randsample() function. Я еще не нашел эффективного способа сделать это.

Итак, я спрашиваю вас, как наилучшим образом случайным образом выбирать k чисел из диапазона 0: n-1 (для n> k) без замены в C++?

Я рассмотрел следующий псевдокод (вдохновленный третьим примером на cppreference.com), но я чувствую, что это немного Hacky:

initialize vect<int> v of size n 
for i = 0 to n-1 
    v[i] = i 
shuffle v 
return v[0 to k-1] 

Недостаток здесь является также требованием, чтобы построить огромный массив первым слишком. Это похоже на медленный/неуклюжий перебор.

Мне понравилось бы какое-то направление здесь, если вы можете помочь. Меня интересует теория (алгоритмы интересны, но не актуальны для моих потребностей сейчас), чем лучший способ реализовать это на C++.

Заранее благодарен!

Answer 1

Вот такой подход, который не требует создания и перетасовки огромный список, в случае N огромен, но k не является:

std::vector<int> pick(int N, int k) { 
    std::random_device rd; 
    std::mt19937 gen(rd()); 

    std::unordered_set<int> elems = pickSet(N, k, gen); 

    // ok, now we have a set of k elements. but now 
    // it's in a [unknown] deterministic order. 
    // so we have to shuffle it: 

    std::vector<int> result(elems.begin(), elems.end()); 
    std::shuffle(result.begin(), result.end(), gen); 
    return result; 
} 

Теперь наивный подход реализации pickSet является:

std::unordered_set<int> pickSet(int N, int k, std::mt19937& gen) 
{ 
    std::uniform_int_distribution<> dis(1, N); 
    std::unordered_set<int> elems; 

    while (elems.size() < k) { 
     elems.insert(dis(gen)); 
    } 

    return elems; 
} 

Но если k большой относительно N, этот алгоритм может привести к большому количеству столкновений и может быть довольно медленным. Мы можем сделать лучше, гарантируя, что мы можем добавить один элемент на каждой вставке (принесла вам Robert Floyd):

std::unordered_set<int> pickSet(int N, int k, std::mt19937& gen) 
{ 
    std::unordered_set<int> elems; 
    for (int r = N - k; r < N; ++r) { 
     int v = std::uniform_int_distribution<>(1, r)(gen); 

     // there are two cases. 
     // v is not in candidates ==> add it 
     // v is in candidates ==> well, r is definitely not, because 
     // this is the first iteration in the loop that we could've 
     // picked something that big. 

     if (!elems.insert(v).second) { 
      elems.insert(r); 
     } 
    } 
    return elems; 
} 

Answer 2

Боб Флойд создал случайный образец алгоритма, который использует множества. Размер промежуточной структуры пропорционален размеру выборки, который вы хотите принять.

Он работает случайным образом генерирует числа K и добавляет их в набор. Если сгенерированный номер уже существует в наборе, он вместо этого помещает значение счетчика, который, как гарантируется, еще не был замечен. Таким образом, он гарантированно работает в линейном времени и не требует большой промежуточной структуры. Он по-прежнему обладает хорошими случайными свойствами распределения.

Этот код в основном снят с программирования Pearls с некоторыми изменениями для использования более современного C++.

unordered_set<int> BobFloydAlgo(int sampleSize, int rangeUpperBound) 
{ 
    unordered_set<int> sample; 
    default_random_engine generator; 

    for(int d = rangeUpperBound - sampleSize; d < rangeUpperBound; d++) 
    { 
      int t = uniform_int_distribution<>(0, d)(generator); 
      if (sample.find(t) == sample.end()) 
       sample.insert(t); 
      else 
       sample.insert(d); 
    } 
    return sample; 
} 

Этот код не проверял.