Выберите m элементов случайным образом из вектора, содержащего n элементов

Question

У меня есть вектор, содержащий n элементов. Мне нужно выбрать подмножество m элементов случайным образом из вектора без повторений. Каков наиболее эффективный способ сделать это? Мне нужно сделать это несколько тысяч раз в моем коде.

Решение, на мой взгляд, заключается в использовании rand() для генерации случайного числа k между 0 и n. Затем выберите k -й элемент в векторе и вставьте его в std::set. Продолжайте делать это, пока размер набора не станет равным m. Теперь я уверен, что набор содержит m уникальных элементов, случайно выбранных из набора n элементов.

Какие есть другие возможные решения?

Спасибо.

Answer 1

Вы хотите перемешивание Фишера-Йейтса (остановка после M итераций):

template<class BidiIter >
BidiIter random_unique(BidiIter begin, BidiIter end, size_t num_random) {
    size_t left = std::distance(begin, end);
    while (num_random--) {
        BidiIter r = begin;
        std::advance(r, rand()%left);
        std::swap(*begin, *r);
        ++begin;
        --left;
    }
    return begin;
}

Демо на http://ideone.com/3A3cv. Это значительно быстрее, чем std::random_shuffle, когда вам нужно всего лишь несколько случайных чисел из набора, и должно быть примерно такой же скорости, даже если N==M.

Answer 2

Один из способов сделать это - создать список всех индексов вектора, перемешать их и взять первые n в качестве индексов выбранных объектов:

struct rangegenerator {
    rangegenerator(int init) : start(init) { }

    int operator()() {
        return start++;
    }

    int start;
};

vector<T> numbers; // this is filled somewhere else

vector<int> indices(numbers.size());

generate(begin(indices), end(indices), rangegenerator(0));

random_shuffle(begin(indices), end(indices));

// then take the first n elements of indices and use them as indices into numbers