Как получить 2 случайных (разных) элемента из вектора c ++

Question

Я хотел бы получить 2 случайных разных элемента из std :: vector. Как я могу сделать это так:

• Это быстро (это делается тысячи раз по моему алгоритму)
• Это элегантно
• Выбор элементов действительно равномерно распределен

Answer 1

Вам нужно сгенерировать М равномерно распределенных случайных чисел из диапазона [0, N), но здесь есть одна оговорка.

Следует отметить, что ваше изложение проблемы неоднозначно. Что подразумевается под равномерно распределенным выбором? Одна вещь состоит в том, чтобы сказать, что каждый индекс должен быть выбран с равной вероятностью (конечно, M / N). Другое дело, что каждая двухиндексная комбинация должна выбираться с равной вероятностью. Эти два не одно и то же. Какой из них вы имели в виду?

Если M значительно меньше, чем N, классическим алгоритмом для выбора чисел M из диапазона [0, N) является алгоритм Боба Флойда, который можно найти в книге Бентли "Programming Peals". Это выглядит следующим образом (эскиз)

for (int j = N - M; i < N; ++j) {

  int rand = random(0, j); // generate a random integer in range [0, j]

  if (`rand` has not been generated before)
    output rand;
  else
    output j;
}

Чтобы реализовать проверку того, был ли rand уже сгенерирован или нет для относительно высокого M, необходима какая-то реализация набора, но в вашем случае M = 2 это просто и легко.

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

Адаптируя вышеизложенное к вашей конкретной ситуации, правильный алгоритм будет выглядеть следующим образом

first = random(0, N - 2);  
second = random(0, N - 1);
if (second == first)
  second = N - 1;

(я опускаю внутренние детали random(a, b) как детали реализации).

Может быть не сразу понятно, почему вышеприведенное работает правильно и дает действительно равномерное распределение, но это действительно так:)

Answer 2

Как насчет использования std::queue и выполнения std::random_shuffle на них. Тогда просто выскакивайте, пока ваше сердце не наполнится?

Answer 3

За элегантность и простоту:

void Choose (const int size, int &first, int &second)
{
  // pick a random element
  first = rand () * size / MAX_RAND;
  // pick a random element from what's left (there is one fewer to choose from)...
  second = rand () * (size - 1) / MAX_RAND;
  // ...and adjust second choice to take into account the first choice
  if (second >= first)
  {
     ++second;
  }
}

с использованием первого и второго для индексации вектора.

Для однородности это очень сложно, так как при приближении размера к RAND_MAX будет смещение к более низким значениям, а если размер превышает RAND_MAX, то будут элементы, которые никогда не будут выбраны. Одним из решений этой проблемы является использование бинарного поиска:

int GetRand (int size)
{
  int lower = 0, upper = size;
  do
  {
    int mid = (lower + upper) / 2;

    if (rand () > RAND_MAX / 2) // not a great test, perhaps use parity of rand ()?
    {
       lower = mid;
    }
    else
    {
       upper = mid;
    }
  } while (upper != lower); // this is just to show the idea,
                            // need to cope with lower == mid and lower != upper
                            // and all the other edge conditions

  return lower;
}

Answer 4

Не элегантно, но очень просто: просто нарисуйте случайное число в [0, vector.size () [и убедитесь, что оно не в два раза больше.

Простота также в некотором роде элегантность;)

Что ты называешь быстрым? Я думаю, это можно сделать тысячи раз за миллисекунду.

Answer 5

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

Answer 6

Всякий раз, когда вам нужно что-то случайное, у вас будут различные вопросы о свойствах случайных чисел, касающихся однородности, распределения и т. Д.

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

Учитывая вектор из N + 1 записей, другой вариант - создать индекс i в диапазоне 0..N. Элемент [я] является первым выбором. Поменяйте местами элементы i и N. Создайте индекс j в диапазоне 0 .. (N-1). element [j] - ваш второй выбор. Это медленно тасует ваш вектор, что может быть проблематично, но этого можно избежать, используя второй вектор, который содержит индексы в первом, и тасуя его. Этот метод торгует свопом для сравнения индексов и имеет тенденцию быть более эффективным для небольших векторов (обычно дюжина или меньше элементов), поскольку он избегает необходимости выполнять множественные сравнения по мере увеличения числа коллизий.