Какой самый эффективный способ выбрать случайную карту из колоды, когда некоторые карты непригодны для использования?

Question

У меня есть массив, который сообщает, используется ли карта:

int used[52];

Это ужасный способ выбрать случайную карту, если у меня много использованных карт:

do {
  card = rand() % 52;
} while (used[card]);

, так как, если у меня будет только 3-4 неиспользованных карты, их поиск займет целую вечность.

Я придумал это:

 int card;
 int k = 0;
 int numUsed = 0;
 for (k=0; k < 52; ++k) {
   if (used[k]) numUsed += 1;
 }
 if (numUsed == 52) return -1;
 card = rand() % (52 - numUsed);

 for (k=0; k < 52; ++k) {
   if (used[k]) continue;
   if (card == 0) return k;
   card -= 1;
 }

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

Какой самый эффективный способ сделать это?

Answer 1

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

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

int sofar = 0;
int selected = -1;
for (i = 0; i < 52; ++i) {
    if (used[i]) continue;
    ++sofar;
    if ((rand() % sofar) == 0) selected = i;
}
if (selected == -1) panic; // there were no usable cards 
else used[selected] = 1;   // we have selected a card

Тогда, если (как вы говорите в комментарии) разные розыгрыши имеют разные критерии, вы можете заменить used[i] на фактические критерии.

Способ работает так, что вы выбираете первую карту. Затем вы заменяете его второй картой с вероятностью 1/2. Замените результат третьей картой с вероятностью 1/3 и т. Д. По индукции легко доказать, что после n шагов вероятность того, что каждая из предыдущих карт будет выбранной, равна 1 / n.

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

Хотя это хорошо и просто.

[Редактировать: доказательство

Пусть p (j, k) будет вероятностью того, что номер карты j будет выбранной в данный момент картой после шага k.

Требуется доказать: для всех n, p (j, n) = 1 / n для всех 1 <= j <= n </p>

Для n = 1, очевидно, p (1,1) = 1, поскольку первая карта выбирается на первом шаге с вероятностью 1/1 = 1.

Предположим, что p (j, k) = 1 / k для всех 1 <= j <= k. </p>

Затем мы выбираем (k + 1) -ю карту на шаге (k + 1) с вероятностью 1 / (k + 1), т.е. p (k + 1, k + 1) = 1 / (k + 1) .

Мы сохраняем существующий выбор с вероятностью k / (k + 1), поэтому для любого j

p(j,k+1) = p(j,k) * k/(k+1)
         = 1/k    * k/(k+1)   // by the inductive hypothesis
         = 1/(k+1)

Итак, p (j, k + 1) = 1 / (k + 1) для всех 1 <= k <= k + 1 </p>

Следовательно, по индукции для всех n: p (j, n) = 1 / n для всех 1 <= j <= n] </p>

Answer 2

Почему бы вам не сохранить еще одну коллекцию неиспользованных карт?

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

Answer 3

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

Answer 4

Стандартный алгоритм раздачи случайных карт:

• инициализировать колоду, чтобы она содержала все карты (порядок не важен)
• цикл:
• генерирует случайный индекс в диапазоне от 0 до размера колоды - 1
• отображать карту с указанным индексом (или делать что угодно)
• поменяйте местами проиндексированную карточку в колоде с карточкой [размер колоды -1]
• уменьшить размер колоды на один
• Перейти к циклу: так часто, как требуется

Answer 5

Другой вариант - иметь два списка, один из которых используется для отслеживания использованных карт, а другой - для отслеживания неиспользованных карт. Поэтому, если вы используете карту, вычтите ее из списка неиспользованных карт и добавьте в конец списка использованных карт. Таким образом, вам не придется каждый раз запускать два цикла for.

Answer 6

Вы можете избавиться от двух циклов, используя такой код:

int card;
int k = 0;
int i = 0;
int unUsed[52];
int numUsed = 0;
for (k = 0; k < 52; ++k) {
  if (used[k]) {
    numUsed += 1;
  } else {
    unUsed[i] = k;
    i++;
  }
}
if (numUsed == 52) return -1;
card = rand() % (52 - numUsed);
return unUsed[card];

Хотя я думаю, что повышение эффективности не будет большим, и вы будете использовать больше памяти.

Answer 7

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

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

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

Answer 8

Knuth Shuffle на многих языках

Answer 9

Храните использованные карты в конце массива и неиспользованные карты в начале. Следите за тем, сколько карт еще не было использовано. При использовании новой карты поменяйте ее последней неиспользованной картой и уменьшите количество оставшихся карт.

if (numRemaining == 0) return -1;
int cardNum = rand() % numRemaining;
Card card = cards[cardNum]; // or int, if cards are represented by their numbers
cards[cardNum] = cards[numRemaining - 1];
cards[numRemaining - 1] = card;
numRemaining--;