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

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

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

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

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

Источник

9 ответов

Решение

Все ответы с использованием % здесь неверны, т.к. 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 случайных битов, но мы забудем об этом здесь.

Источник

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

#include  <random>
#include  <iterator>

template<typename Iter, typename RandomGenerator>
Iter select_randomly(Iter start, Iter end, RandomGenerator& g) {
    std::uniform_int_distribution<> dis(0, std::distance(start, end) - 1);
    std::advance(start, dis(g));
    return start;
}

template<typename Iter>
Iter select_randomly(Iter start, Iter end) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    return select_randomly(start, end, gen);
}

Пример использования:

#include <vector>
using namespace std;

vector<int> foo;
/* .... */
int r = *select_randomly(foo.begin(), foo.end());

Я закончил тем, что создал суть с лучшим дизайном, следуя аналогичному подходу.

Источник

C++17 std::sample

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

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

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

Проверено в g++ 7.2, с g++ -std=c++17 Ubuntu 17.10. Используйте это для Ubuntu 16.04.

Источник

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

vector<int>::iterator randIt = myvector.begin();
std::advance(randIt, std::rand() % myvector.size());
Источник

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

#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;
}
Источник

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

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

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

Источник

Вы можете попытаться получить случайное число от 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);
Источник 
      #include <vector>
using std::vector;

vector<int> vi = {1, 2, 3, 4, 5};
srand(time(0));
randomPosition = rand() % vi.size();
randomElement = vi[randomPosition]

srand(time(0))семя для случайного, если его не использовать, оно будет получать одно и то же случайное целое число при каждом выполнении.

Источник

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

Источник
Другие вопросы по тегам