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

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

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

Ответы

Ответ 1

Вы хотите Fisher-Yates shuffle (остановка после 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.

Ответ 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