Реальные проблемы с наивным тасованием

Question

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

Как Джефф Этвуд указывает на CodingHorror.com , один простой метод перетасовки (перебор массива и замена каждой карты случайной картой в другом месте массива) создает неравномерное распределение перестановок. В реальном приложении я бы просто использовал Кнута Фишера-Йейтса для более равномерной случайности. Но я не хочу увязывать объяснение концепций программирования с гораздо менее дружественным к кодировщику алгоритмом.

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

Answer 1

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

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

Answer 2

Оказывается, преимущество довольно значительное. Проверьте эту статью

Часть проблемы - некорректный алгоритм, но другая часть - предположение, что вы можете получить «случайные» числа с компьютера.

Answer 3

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

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

Answer 4

Кроме того, на ITtoolbox было опубликовано сообщение в блоге о перетасовке, которое может представлять интерес, когда речь заходит о симуляции перетасовки.

Что касается вашего вопроса, считайте, что их 52! Конфигурации колоды, с которых можно начать, могут сыграть роль в том, где что-либо приземляется, как в примере Джеффа с колодой из трех карт, обратите внимание, что 1 в перепредставленном виде встречается в каждом слоте один раз. Также обратите внимание, что он говорит, что вам нужно иметь несколько тысяч примеров, прежде чем станет очевидно, где преимущество, но с колодой вы вряд ли начнете снова с той же самой начальной колоды, не так ли? Вы бы взяли сданные карты и положили их на дно и перетасовали их, что вряд ли повторится, я думаю.

Answer 5

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

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

Answer 6

Субъективная.

Кажется, это было бы бесконечно мало.

Согласен.