Почему fisher yates - самый полезный алгоритм тасования?

Question

Можете ли вы сказать, что современная версия fisher yates - самый беспристрастный алгоритм тасования? Как бы вы объяснили, что каждый элемент в массиве имеет вероятность того, что 1 / n окажется в своем первоначальном месте?

Answer 1

Учитывая идеальный генератор псевдослучайных чисел ( Mersenne Twister очень близок), алгоритм Фишера-Йейтса совершенно беспристрастен в том смысле, что каждая перестановка имеет равную вероятность возникновения. Это легко доказать с помощью индукции. Алгоритм Фишера-Йейтса можно записать рекурсивно следующим образом (в псевдокоде синтаксиса Python):

def fisherYatesShuffle(array):
    if len(array) < 2:
        return

    firstElementIndex = uniform(0, len(array))
    swap(array[0], array[firstElementIndex])
    fisherYatesShuffle(array[1:])

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

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

Answer 2

the (Modern, он же «Кнут») Фишер – Йейтс случайное число

• относительно просто реализовать
• довольно эффективный O (n) для времени и O (1) или действительно O (0) для пространства
• беспристрастно (каждая перестановка равновероятна)
• хорошо известно / хорошо понято, проверено, проверено.

Что еще мы могли бы хотеть от алгоритма (ну, да, когда число перестановок становится огромным, можно попробовать что-то еще, но в большинстве случаев такие огромные количества не учитываются)?

Редактировать : 'только что заметил, что этот ответ отвечает на заголовок вопроса, а не на содержание . (Вот почему хорошо, чтобы эти две части вопроса соответствовали лучше ...)
В двух словах, случайное перемешивание будет столь же случайным, как конкретный ГСЧ, использованный для реализации алгоритма .
Интуитивно понятное объяснение состоит в том, что для массива с элементом m, даже несмотря на то, что при n нисходящая управляющая переменная цикла уменьшается в направлении 1, возможные ячейки, в которых ячейка в позиции n может поменяться местами, уменьшаются, вероятность того, что эта ячейка был легко перемещен увеличивается в той же пропорции. Другими словами, последний элемент массива может оказаться в любом месте массива, но у него есть только один шанс для перемещения (после самой первой итерации). У второго до последнего элемента, подлежащего перемещению, требуется меньше места, но существует вероятность 1 / m, что он мог быть легко перемещен во время самой первой итерации. и т.д.