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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

Субъективно.

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

Соглашайся.

Answer 6

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

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