Разница между алгоритмами тасования

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

Один алгоритм будет:

  • Заполните массив из 52 элементов: 1 для первого элемента, 2 для второго и т. Д.
  • Напишите цикл for, который повторяет X раз, и во время каждой итерации выбирайте две случайные карты и меняйте их местами.
  • Чем больше X, тем более случайным будет случайное перемешивание.

Другой алгоритм:

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

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

Источник

4 ответа

Решение

Второй алгоритм, по-видимому, представляет собой развернутую на двоих реализацию Фишера-Йейтса. Эта случайность имеет свойство выбора одного из всех возможных результатов с равномерным распределением. То, что большинство назвало бы "честным" или "идеальным" перемешиванием. Нет необходимости повторять операцию для дополнительной случайности, если ваш генератор случайных чисел обеспечивает непредвзятые результаты.

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

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

Источник

Первый алгоритм производит сильно смещенное распределение, поскольку он может оставить некоторые карты в их исходном положении и уязвимыми для проблемы "двойной замены" (замена двух одинаковых карт дважды приводит к исходному состоянию карт).

Второй алгоритм, как упомянуто @sh1, является развернутой версией алгоритма Фишера-Йейтса, за одним небольшим исключением: он больше не является линейным, поскольку удаление элементов из списка само по себе является линейной операцией и выполняется на каждой итерации, поэтому общая сложность алгоритма O(N ^2).

Эффективная версия алгоритма Фишера-Йейтса будет следующей:

В псевдокоде (так как вы не упомянули язык по выбору)

for i from n − 1 downto 1 do
   j ← random integer with 0 ≤ j ≤ i
   exchange a[j] and a[i]

И реализация Python, на всякий случай:)

import random
n = 52
arr = [i for i in range(1,n+1)]

for i in range(n-1, 1, -1):
    elem_to_swap = random.randint(0, i)
    arr[elem_to_swap], arr[i] = arr[i], arr[elem_to_swap]
Источник

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

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

Я бы либо запускал алгоритм 2 раза, либо тасовал карты, как вы делаете настоящую колоду

1: Split the deck into two arrays of 26
2: Take the top card from one of the arrays at random and put it into a new array of size 52
3: Keep doing this until one array is empty, put the remaining cards of the other array into the size 52 array
4: Repeat

Это даст вам хорошую рандомизацию

Источник

Лучше один это:

  1. Генерация 52 числа в некотором временном массиве
  2. Закажите массив с картами, используя временный массив в качестве ключа

в C# это выглядит

Random r = new Random(DateTime.Now.Miliseconds);
string [] cards = new string[52]{"1","2",.....};
int [] temp = new int[52];
for(int i=0;i<52;i++)
{
    temp[i]=r.Next();
}

Array.Sort(temp,cards);
Источник
Другие вопросы по тегам