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

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

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

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

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

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

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

 template  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 :: uniform_int_distribution:

 #include  #include  template 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 Iter select_randomly(Iter start, Iter end) { static std::random_device rd; static std::mt19937 gen(rd()); return select_randomly(start, end, gen); } 

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

 #include  using namespace std; vector foo; /* .... */ int r = *select_randomly(foo.begin(), foo.end()); 

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

C ++ 17 std::sample

Это удобный метод:

 #include  #include  #include  #include  int main() { std::vector in{1, 2, 3, 5, 7}, out; std::sample(in.begin(), in.end(), std::back_inserter(out), 3, 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.

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

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

 #include  #include  template  InputIterator random_n(InputIterator first, InputIterator last) { typename std::iterator_traits::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  InputIterator random_n(InputIterator first, InputIterator last, RandomGenerator& rand) { typename std::iterator_traits::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  #include  // ... 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); 

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

  • Какая целочисленная hash-функция хороша, которая принимает целочисленный хеш-ключ?
  • Быстрый точный масштабный факториал
  • Быстрые и простые комбинации hash-кодов
  • Сумма-подмножество с фиксированным размером подмножества
  • Вычислить наибольший прямоугольник во вращающемся прямоугольнике
  • Генерация перетасованного диапазона с использованием PRNG, а не перетасовка
  • Как работают тригонометрические функции?
  • Как найти подключенные компоненты в Matlab?
  • Что может привести к сложности алгоритма O (log n)?
  • Что такое алгоритм Hi / Lo?
  • Пиковое обнаружение измеренного сигнала
  • Interesting Posts

    Как узнать, работает ли мой процесс в качестве администратора?

    Почему мое DSL-соединение так медленно, когда мой сосед намного быстрее?

    Entity Framework 4.1 загрузка по умолчанию по умолчанию

    Как настроить настраиваемые обработчики URL-адресов в OS X?

    Как анализировать аргументы командной строки на C ++?

    привязки, не разрешающие обработку АСТ в eclipse

    Используйте DSL-модем / беспроводной маршрутизатор в качестве немого беспроводного маршрутизатора

    Быстрый простой способ миграции SQLite3 в MySQL?

    Ffmpeg последовательность изображений

    Является ли это очень важным для производительности?

    Создайте токен доступа «никогда не истекающий» для страницы Facebook

    Как читать данные в формате PDF с помощью iTextSharp?

    Ошибка чтения диска всякий раз, когда я устанавливаю XP pro

    Найти k-й наименьший элемент в двоичном дереве поиска Оптимальным способом

    Векторизованные шрифты в формате PDF для монтажа ImageMagick?

    Давайте будем гением компьютера.