Как получить случайный элемент из контейнера C ++?

Question

Какой хороший способ получить [псевдо-] случайный элемент из диапазона STL?

Лучшее, что я могу придумать, это сделать std::random_shuffle(c.begin(), c.end()), а затем взять мой случайный элемент из c.begin().

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

Есть ли лучший способ?

Answer 1

Я разместил это решение в статье в Google+, где кто-то другой ссылался на это.Публикуем его здесь, так как этот немного лучше, чем другие, потому что он позволяет избежать смещения, используя std :: .: Суть с лучшим дизайном, следуя аналогичному подходу .

Answer 2

Все ответы, использующие %, здесь неправильные, поскольку rand() % n даст смещенные результаты: представьте RAND_MAX == 5 и количество элементов равно 4. Тогда вы получите вдвое больше чисел 0 и 1, чем чисел2 или 3.

Правильный способ сделать это:

template <typename I>
I random_element(I begin, I end)
{
    const unsigned long n = std::distance(begin, end);
    const unsigned long divisor = (RAND_MAX + 1) / n;

    unsigned long k;
    do { k = std::rand() / divisor; } while (k >= n);

    std::advance(begin, k);
    return begin;
}

Другая проблема состоит в том, что std::rand предполагается только иметь 15 случайных битов, но мы забудем об этомздесь.

Answer 3

C ++ 17 std::sample

Это удобный метод для получения нескольких случайных элементов без повторений.

main.cpp

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

int main() {
    const std::vector<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    size_t nelems = 3;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                nelems, std::mt19937{std::random_device{}()});
    for (auto i : out)
        std::cout << i << std::endl;
}

Компиляция и запуск:

g++-7 -o main -std=c++17 -Wall -Wextra -pedantic main.cpp
./main

Вывод: 3 случайных числа выбираются из 1, 2, 3, 5, 7 без повторений.

Для эффективности только O(n) являетсягарантировано, поскольку ForwardIterator является используемым API, но я думаю, что реализации stdlib будут специализироваться на O(1), где это возможно (например, vector).

Протестировано в GCC 7.2, Ubuntu 17.10. Как получить GCC 7 в 16.04 .

Answer 4

Это прекрасно работает, пока RAND_MAX намного больше, чем размер контейнера, в противном случае он страдает от проблемы смещения , цитируемой Александром :

vector<int>::iterator randIt = myvector.begin();
std::advance(randIt, std::rand() % myvector.size());

Answer 5

Если вы не можете получить доступ к размеру, я думаю, вы захотите сделать следующее.Возвращает итератор к случайному элементу.

#include <algorithm>
#include <iterator>

template <class InputIterator> InputIterator 
random_n(InputIterator first, InputIterator last) {
   typename std::iterator_traits<InputIterator>::difference_type distance = 
        std::distance(first, last);
   InputIterator result = first;
   if (distance > 1) {
      // Uses std::rand() naively.  Should replace with more uniform solution. 
      std::advance( result, std::rand() % distance );
   }
   return result;
}
// Added in case you want to specify the RNG.  RNG uses same 
// definition as std::random_shuffle
template <class InputIterator, class RandomGenerator> InputIterator 
random_n(InputIterator first, InputIterator last, RandomGenerator& rand) {
   typename std::iterator_traits<InputIterator>::difference_type distance = 
       std::distance(first, last);
   InputIterator result = first;
   if (distance > 1) {
      std::advance( result, rand(distance) );
   }
   return result;
}

Answer 6

Возьмите количество элементов, c.size(), затем получите random_number между 0 и c.size() и используйте:

auto it = c.begin();
std::advance(it, random_number)

Посмотрите на http://www.cplusplus.com/reference/clibrary/cstdlib/rand/

Answer 7

Вы можете попытаться получить случайное число от 0 до количества элементов контейнера.Затем вы можете получить доступ к соответствующему элементу контейнера.Например, вы можете сделать это:

#include <cstdlib>
#include <ctime>

// ...
std::srand(std::time(0)); // must be called once at the start of the program
int r = std::rand() % c.size() + 1; 
container_type::iterator it = c.begin();
std::advance(it, r);

Answer 8

Вы можете использовать 0 ~ 1 случайную функцию для генерации числа с плавающей запятой для каждого элемента в контейнере в качестве его оценки. А затем выберите тот, который набрал наибольшее количество баллов.