Как и в качестве фона, я знаю, что Fisher-Yates отлично перемешивается. Это отличная перетасовка с ее сложностью O (n) и ее гарантированной однородностью, и я был бы дураком, чтобы не использовать ее... в среде, которая позволяет на месте обновления массивов (так что в большинстве, если не все, императивные среды программирования).
К сожалению, мир функционального программирования не дает вам доступ к изменяемому состоянию.
Из-за Fisher-Yates, однако, не так много литературы, которую я могу найти о том, как разработать алгоритм перетасовки. Несколько мест, которые обращаются к нему, делают это кратко, прежде чем сказать, по сути, "так вот, Фишер-Йейтс, который все перетасовывает вам нужно знать". В конце концов, мне пришлось придумать свое решение.
Решение, которое я придумал, похоже на это, чтобы перетасовать любой список данных:
- Если список пуст, верните пустой набор.
- Если в списке есть один элемент, верните этот единственный элемент.
- Если список не пуст, разделите список на генератор случайных чисел и примените алгоритм рекурсивно к каждому разделу, собрав результаты.
В коде Erlang это выглядит примерно так:
shuffle([]) -> [];
shuffle([L]) -> [L];
shuffle(L) ->
{Left, Right} = lists:partition(fun(_) ->
random:uniform() < 0.5
end, L),
shuffle(Left) ++ shuffle(Right).
(Если это выглядит как неудобный быстрый вид для вас, ну, что это такое, в основном.)
Итак, вот моя проблема: та же ситуация, которая затрудняет поиск алгоритмов перетасовки, которые не являются Fisher-Yates, затрудняет поиск инструментов анализировать алгоритм перетасовки. Там есть много литературы, которую я могу найти при анализе PRNG для единообразия, периодичности и т.д., Но не так много информации о том, как анализировать перетасовку. (Действительно, некоторая информация, которую я обнаружил при анализе перетасовки, была просто ошибочной - легко обмануть с помощью простых методов.)
Итак, мой вопрос заключается в следующем: как я могу проанализировать мой алгоритм перетасовки (при условии, что вызов random:uniform() доходит до задачи генерации подходящих случайных чисел с хорошими характеристиками)? Какие математические инструменты существуют в моем распоряжении, чтобы судить о том, действительно ли 100 000 пробегов перетасования над списком целых чисел в диапазоне 1..100 дали мне правдоподобные хорошие результаты перетасовки? Я сделал несколько собственных тестов (например, сравнивая приращения с декрементами в случайном порядке), но я хотел бы узнать еще несколько.
И если есть какое-либо понимание этого алгоритма тасования, это тоже было бы оценено.
