Comments 22
Это выглядит довольно бесхитростно, хотя хотелось бы, чтобы в C# была команда Swap()
https://learn.microsoft.com/ru-ru/dotnet/api/system.random.shuffle?view=net-9.0
Разве Shuffle в данном случае не делает то же самое?
Да - под капотом всех шаффлов - перестановки Кнута.
Алгоритм работающий за линию и на выходе дающий честные* 1/n вероятности попадания для каждого элемента в любое место на выходе.
У Кнута в его "Искусстве программирования" есть доказателство.
*настолько честные - насколько ваш рандом "честен"
п.с. лет 10 на собесах давал эту задачу и следом "а как бы вы протестили что ваше решение дает честные 1/n"
Спорна сама уверенность в "лучшести" некого алгоритма генерации случайного числа. Бросая кости, вы же не мыслите логикой. что следующее число очков будет зависеть от результата предыдущего броска.
Немного завидую людям, способным настолько упарываться в простые, на первый взгляд, и, честно говоря, не особо важные вопросы
Автор не умеет в лаконичность. Например, весь параграф про недостаток наивного алгоритма можно выразить одним предложением, что n^n не делится на n!, потому что n и (n-1) взаимно просты, и значит перестановки распределятся не поровну по исходам.
В древней Спарте такая подача материала не сошла бы автору с рук.
Ох уж эти математические дискурсы на кулаках, которыми известна древняя Спарта. Вы допускаете, что автор написал понятнее для тех, кто лучше понимает формулы + текстовые описания? Тем более это перевод.
А причем тут кулаки, если речь про лаконичность
var shuffledcards = cards.OrderBy(a => Guid.NewGuid());
Я представил, что было бы, если бы нынешние оптимизаторы сишных компиляторов добрались до дотнета. Они бы всем показали. Если Guid.NewGuid() не является полем a, значит программист сам не знает, чего хочет, а дальше было бы как в анекдоте про return 4; // Random enough.
написано синхронизация по времени и далее предлагается очень нагрузный алгоритм KFY - я посмотрел на картинке его алгоритм первое о чем подумал что он еще проще предсказуем, перечитал еще раз участок текста с синхронизацией посмотрел граффик и пока ничего не понял(чтобы сделать ту синхронизацию наверняка надо всё понимать еще лучше чем с такой сортировкой)
сортировать по некоторому Guid
Так Guid сам под капотом использует рандом, разве нет? Общей энтропии конечно больше ест, но при размере массива в 52 элемента уровень случайности перемешивания лучше едва ли станет.
Вспоминается университетская лабораторная по криптографии — всех подробностей уже не восстановить, но среди прочего тоже нужно было случайно перемешать массив.
Я придумал, как мне тогда казалось, ловкое и практичное решение: завёл второй массив той же длины, заполнил его случайными числами, а потом отсортировал, при этом зеркально повторяя все перестановки в основном массиве.
Кто-то нашёл в статье чёткий критерий "качества" перемешивания?
Там раза три написано. Перемешано качественно означает что вероятность любого расклада (порядка карт в колоде) одинакова.
Ещё один эквивалентный критерий, который иногда удобнее в доказательстве — это то, что каждый элемент на каждой позиции окажется равновероятно.
каждый элемент на каждой позиции окажется равновероятно
Не назвал бы эквивалентным. Пример таблицы вероятностей:
Скрытый текст
123 - 33.(3)%
132 - 0%
231 - 33.(3)%
213 - 0%
312 - 33.(3)%
321 - 0%
Каждый элемент на каждой позиции встречается равновероятно, но при этом вероятность у отдельных комбинаций совершенно разная.
К замечанию про рандом-из-миллисекунд хочу добавить, что давно пора форсировать, что все random-ы по умолчанию используют максимально честный криптографический недетерминированный рандом (если не аппаратный генератор, то хотя бы Yarrow или Fortuna), а детерминированные оставить для математиков с явно помеченными именами.
Ну а наивный переставлятор... изначально плохо пах. Но чтобы это из ощущения превратить в твёрдый вывод, тут и нужна математика.
К правильному решению можно прийти проще. Что нам надо сделать? Перемешивание. Точнее, модель реального перемешивания. Как выглядит реальное перемешивание? Берем несколько карт из случайной позиции, и помещаем в другое место среди других карт. Для лучшего перемешивания надо брать по одной. Что означает "берем"? Что мы физически убираем карту из колоды. Когда она перемещается в другую позицию, она находится в руке, а не в колоде.
Значит в коде, который моделирует процесс перемешивания, должно быть 2 списка карт. Второй изначально пустой. Берем случайный индекс от 0 до длины первого списка, убираем карту из первого списка, добавляем во второй. Суммарная длина двух списков всегда равна длине исходного, поэтому можно оптимизировать и использовать конец первого списка как второй список. А вместо сдвигов нескольких карт в первом списке на 1 элемент можно ставить на пустое место последнюю карту, все равно индексы случайные.
Опасность наивности