Что, если что-то не так, с этим алгоритмом перетасовки, и как я могу узнать?

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

К сожалению, мир функционального программирования не дает вам доступа к изменяемому состоянию.

Однако из-за Фишера-Йейтса я не могу найти много литературы по как разработать алгоритм перемешивания. Те немногие места, которые вообще обращаются к нему, делают это вкратце, прежде чем, по сути, сказать: «Итак, вот Фишер-Йейтс, это все, что вам нужно знать». В конце концов, мне пришлось придумать собственное решение.

Решение, которое я придумал, работает следующим образом: перетасовка любого списка данных:

• Если список пуст, вернуть пустой набор.
• ] Если в списке есть один элемент, вернуть этот единственный элемент.
• Если список не пуст, разделите список с помощью генератора случайных чисел и рекурсивно примените алгоритм к каждому разделу, собирая результаты.

В коде Erlang это выглядит примерно так:

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(Если вам кажется, что это ненормальная быстрая сортировка, ну, по сути, так оно и есть.)

Итак, вот моя проблема: та же ситуация, которая затрудняет поиск алгоритмов перетасовки, отличных от Фишера-Йейтса, делает поиск инструменты для анализа алгоритма перетасовки одинаково трудны. Я могу найти много литературы по анализу ГПСЧ на предмет однородности, периодичности и т. Д., Но не так много информации о том, как анализировать перемешивание. (Действительно, часть информации, которую я нашел при анализе перемешивания, была просто неправильной - ее легко обмануть с помощью простых методов. )

Итак, мой вопрос заключается в следующем: как мне проанализировать свой алгоритм перетасовки (если предположить, что вызов random: uniform () подходит для задачи генерации подходящих случайных чисел с хорошими характеристиками)? Какие математические инструменты есть в моем распоряжении, чтобы судить о том, дали ли мне, скажем, 100 000 прогонов тасовки по списку целых чисел от 1 до 100 приемлемо хорошие результаты тасования? Я провел несколько собственных тестов (например, сравнивая приращения с убыванием при перемешивании), но я хотел бы узнать еще несколько.

И если есть хоть какое-то представление о самом алгоритме перемешивания, это будет тоже оценили.