Как перетасовать std :: vector?

97

Я ищу универсальный способ многоразового перетасовки std::vectorв C ++. Вот как я сейчас это делаю, но я думаю, что это не очень эффективно, потому что ему нужен промежуточный массив, и он должен знать тип элемента (DeckCard в этом примере):

srand(time(NULL));

cards_.clear();

while (temp.size() > 0) {
    int idx = rand() % temp.size();
    DeckCard* card = temp[idx];
    cards_.push_back(card);
    temp.erase(temp.begin() + idx);
}
Лоран
источник
Нет. ищите рыбака-йейтса ....
Митч Уит
3
Старайтесь не использовать rand(), есть более подходящие API-интерфейсы RNG (Boost.Random или 0x <random>).
Cat Plus Plus
Связано

Ответы:

202

Начиная с C ++ 11, вы должны предпочесть:

#include <algorithm>
#include <random>

auto rng = std::default_random_engine {};
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Live example on Coliru

Не забудьте повторно использовать один и тот же экземпляр в rngнескольких вызовах, std::shuffleесли вы собираетесь каждый раз генерировать разные перестановки!

Более того, если вы хотите, чтобы ваша программа создавала разные последовательности перемешивания каждый раз при запуске, вы можете заполнить конструктор случайного механизма выводом std::random_device:

auto rd = std::random_device {}; 
auto rng = std::default_random_engine { rd() };
std::shuffle(std::begin(cards_), std::end(cards_), rng);

Для C ++ 98 вы можете использовать:

#include <algorithm>

std::random_shuffle(cards_.begin(), cards_.end());
user703016
источник
8
Вы также можете подключить пользовательский генератор случайных чисел в качестве третьего аргумента std::random_shuffle.
Александр С.
19
+1 - Обратите внимание, что это может приводить к одинаковому результату при каждом запуске программы. Вы можете добавить настраиваемый генератор случайных чисел (который может быть загружен из внешнего источника) в качестве дополнительного аргумента, std::random_shuffleесли это проблема.
Mankarse 03
4
@ Gob00st: он будет генерировать одинаковый результат для каждого экземпляра программы, а не при каждом вызове random_shuffle. Это нормальное и преднамеренное поведение.
user703016 03
3
@ TomášZato#include <algorithm>
user703016 07
4
@ ParkYoung-Bae Спасибо, я только что узнал . Это действительно неудобно, когда ответы SO не содержат информации, потому что они находятся в верхней части результатов поиска Google.
Tomáš Zato - Reinstate Monica
10

http://www.cplusplus.com/reference/algorithm/shuffle/

// shuffle algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::shuffle
#include <vector>       // std::vector
#include <random>       // std::default_random_engine
#include <chrono>       // std::chrono::system_clock

int main () 
{
    // obtain a time-based seed:
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine e(seed);

    while(true)
    {
      std::vector<int> foo{1,2,3,4,5};

      std::shuffle(foo.begin(), foo.end(), e);

      std::cout << "shuffled elements:";
      for (int& x: foo) std::cout << ' ' << x;
      std::cout << '\n';
    }

    return 0;
}
Мехмет Фиде
источник
плохой пример скопирован с cplusplus.com/reference/algorithm/shuffle . Как сделать еще один звонок в случайном порядке?
miracle173
@ miracle173 пример улучшен
Mehmet Fide
2
Почему странное использование системных часов для семени вместо простого использования std::random_device?
Чак Уолбурн
6

В дополнение к тому, что сказал @Cicada, вам, вероятно, следует сначала посеять,

srand(unsigned(time(NULL)));
std::random_shuffle(cards_.begin(), cards_.end());

Комментарий @FredLarson:

источник случайности для этой версии random_shuffle () определяется реализацией, поэтому она может вообще не использовать rand (). Тогда srand () не будет иметь никакого эффекта.

Итак, YMMV.


источник
11
Фактически, источник случайности для этой версии random_shuffle()определяется реализацией, поэтому она может вообще не использоваться rand(). Тогда не srand()будет никакого эффекта. Я уже сталкивался с этим раньше.
Фред Ларсон
@Fred: Спасибо, Фред. Не знал этого. Я привык постоянно пользоваться srand.
6
Вам, вероятно, следует удалить этот ответ, поскольку он неверен и, что еще хуже, он кажется правильным и действительно правильным в некоторых реализациях, но не во всех, что делает этот совет очень опасным.
Томас Бонини
2
Как объяснил @Fred выше, то, что random_shuffleиспользуется для генерации случайного числа, определяется реализацией. Это означает, что в вашей реализации он использует rand()(и, следовательно, srand () работает), но в моей он может использовать что-то совершенно другое, а это означает, что в моей реализации даже с srand каждый раз, когда я запускаю программу, я получаю те же результаты.
Томас Бонини
2
@Code: как мы уже обсуждали, он работает не во всех реализациях. Тот факт, что вы можете предоставить свою собственную генерацию номеров, не упоминается в вашем ответе и в любом случае не имеет отношения к этому обсуждению. Я чувствую, что мы ходим по кругу: S
Томас Бонини
2

Если вы используете boost, вы можете использовать этот класс ( debug_modeустановлен в false, если вы хотите, чтобы рандомизация могла быть предсказуемой между выполнением, вы должны установить его true):

#include <iostream>
#include <ctime>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <boost/random/variate_generator.hpp>
#include <algorithm> // std::random_shuffle

using namespace std;
using namespace boost;

class Randomizer {
private:
    static const bool debug_mode = false;
    random::mt19937 rng_;

    // The private constructor so that the user can not directly instantiate
    Randomizer() {
        if(debug_mode==true){
            this->rng_ = random::mt19937();
        }else{
            this->rng_ = random::mt19937(current_time_nanoseconds());
        }
    };

    int current_time_nanoseconds(){
        struct timespec tm;
        clock_gettime(CLOCK_REALTIME, &tm);
        return tm.tv_nsec;
    }

    // C++ 03
    // ========
    // Dont forget to declare these two. You want to make sure they
    // are unacceptable otherwise you may accidentally get copies of
    // your singleton appearing.
    Randomizer(Randomizer const&);     // Don't Implement
    void operator=(Randomizer const&); // Don't implement

public:
    static Randomizer& get_instance(){
        // The only instance of the class is created at the first call get_instance ()
        // and will be destroyed only when the program exits
        static Randomizer instance;
        return instance;
    }

    template<typename RandomAccessIterator>
    void random_shuffle(RandomAccessIterator first, RandomAccessIterator last){
        boost::variate_generator<boost::mt19937&, boost::uniform_int<> > random_number_shuffler(rng_, boost::uniform_int<>());
        std::random_shuffle(first, last, random_number_shuffler);
    }

    int rand(unsigned int floor, unsigned int ceil){
        random::uniform_int_distribution<> rand_ = random::uniform_int_distribution<> (floor,ceil);
        return (rand_(rng_));
    }
};

Затем вы можете проверить это с помощью этого кода:

#include "Randomizer.h"
#include <iostream>
using namespace std;

int main (int argc, char* argv[]) {
    vector<int> v;
    v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
    v.push_back(6);v.push_back(7);v.push_back(8);v.push_back(9);v.push_back(10);

    Randomizer::get_instance().random_shuffle(v.begin(), v.end());
    for(unsigned int i=0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    return 0;
}
Madx
источник
Почему вы используете время, чтобы заполнить генератор, а не std::random_device?
Чак Уолборн
1

Это может быть еще проще, можно полностью избежать посева:

#include <algorithm>
#include <random>

// Given some container `container`...
std::shuffle(container.begin(), container.end(), std::random_device());

Это приведет к новому перемешиванию при каждом запуске программы. Мне также нравится такой подход из-за простоты кода.

Это работает, потому что все, что нам нужно, std::shuffleэто a UniformRandomBitGenerator, чьи требования std::random_deviceсоответствуют.

Примечание: при многократном перемешивании может быть лучше сохранить random_deviceв локальной переменной:

std::random_device rd;
std::shuffle(container.begin(), container.end(), rd);
Apollys поддерживает Монику
источник
2
Что это добавляет, чего еще не было в принятом ответе 8 лет назад?
ChrisMM
1
Все, что вам нужно сделать, это прочитать ответ, чтобы узнать ... Больше нечего сказать, что еще не было очень четко объяснено выше.
Apollys поддерживает Монику
1
В принятом ответе уже используется перемешивание и предлагается использовать random_device...
ChrisMM 06
1
Старый принятый ответ может быть более подробным. Тем не менее, это как раз тот однолинейный ответ, который я ожидал, когда искал в Google такой простой вопрос без особых церемоний. +1
Ichthyo
2
Это неправильно . random_deviceпредназначен для вызова только один раз для заполнения ГПСЧ, а не для повторного вызова (что может быстро исчерпать базовую энтропию и привести к переключению на неоптимальную схему генерации)
LF