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

С++. Visual Studio 2010.

У меня есть std::vector V из N уникальных элементов (heavy). Как эффективно выбрать M случайных, уникальных элементов из него?

например. V содержит 10 элементов: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} и я выбираю три...

4, 0, 9
0, 7, 8
Но НЕ это: 0, 5, 5 < --- не уникально!

STL является предпочтительным. Итак, что-то вроде этого?

std::minstd_rand gen; // linear congruential engine??
std::uniform_int<int> unif(0, v.size() - 1);
gen.seed((unsigned int)time(NULL));

// ...?

// Or is there a good solution using std::random_shuffle for heavy objects?

Ответ 1

Создайте произвольную перестановку диапазона 0, 1, ..., N - 1 и выберите первый M из них; используйте их как индексы в свой исходный вектор.

Случайная перестановка легко выполняется с помощью стандартной библиотеки, используя std::iota вместе с std::random_shuffle:

std::vector<Heavy> v; // given

std::vector<unsigned int> indices(V.size());
std::iota(indices.begin(), indices.end(), 0);
std::random_shuffle(indices.begin(), indices.end());

// use V[indices[0]], V[indices[1]], ..., V[indices[M-1]]

Вы можете предоставить random_shuffle генератор случайных чисел по вашему выбору; проверьте документацию и застенчивость, мужчины и стеснительность для деталей.

Ответ 2

В большинстве случаев метод, предоставляемый Kerrek, является достаточным. Но если N очень велико, а M на порядок меньше, может быть предпочтительным следующий метод.

Создайте набор целых чисел без знака и добавьте к нему случайные числа в диапазоне [0, N-1], пока размер набора не будет равен M. Затем используйте элементы в этих индексах.

std::set<unsigned int> indices;
while (indices.size() < M)
    indices.insert(RandInt(0,N-1));

Ответ 3

Поскольку вы хотели, чтобы он был эффективным, я думаю, вы можете получить амортизированный O(M), предполагая, что вам нужно выполнять эту операцию много раз. Однако этот подход не является реентерабельным.

Прежде всего создайте локальный (т.е. static) вектор std::vector<...>::size_type (т.е. unsigned).

Если вы введете свою функцию, измените размер вектора на соответствие N и заполните его значениями от старого размера до N-1:

static std::vector<unsigned> indices;
if (indices.size() < N) {
  indices.reserve(N);
  for (unsigned i = indices.size(); i < N; i++) {
    indices.push_back(i);
  }
}

Затем случайным образом выбираем M уникальные числа из этого вектора:

std::vector<unsigned> result;
result.reserver(M);
for (unsigned i = 0; i < M; i++) {
  unsigned const r = getRandomNumber(0,N-i); // random number < N-i
  result.push_back(indices[r]);
  indices[r] = indices[N-i-1];
  indices[N-i-1] = r;
}

Теперь ваш результат сидит в векторе result.

Тем не менее, вам все равно придется исправлять свои изменения до indices для следующего прогона, так что indices снова монотонно:

for (unsigned i = N-M; i < N; i++) {
  // restore previously changed values
  indices[indices[i]] = indices[i];
  indices[i] = i;
}

Но этот подход полезен только в том случае, если вам нужно много раз запускать этот алгоритм, а N не настолько велик, что вы не можете жить с indices едой RAM все время.