Метод генерации случайной перестановки, алгоритм Фишера-Йетса

Постановка задачи

Необходимо сгенерировать случайную перестановку из [math] n [/math] чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.

Решение

Пусть

• random(1..i); генерирует случайное число в интервале [math] [1; i] [/math]
  
• swap(i, j); меняет местами числа на местах i и j в массиве [math] a[\;][/math]
  
• и пусть для определенности массив задан: [math] a[\;] = \lt 1, 2, 3, ..., (n-1), n\gt [/math]
  

Следующий алгоритм решает задачу:

 for i = 1..n
   swap(i, random(1..i))

Этот алгоритм носит имя Фишера-Йетса.

Обоснование

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

• при [math] n = 1 [/math] перестановка всего одна, и, очевидно, что база верна
• пусть при [math] n = k - 1 [/math] каждая перестановка равновероятна, то есть вероятность отдельно взятой перестановки [math] \frac {1}{(k-1)!}[/math]

[math] a[\;] = \lt a_{1}, a_{2}, ..., a_{n-1}, n\gt [/math]

после swap(i, random(1..i)) вероятность какого-то числа оказаться на n-ом месте равна [math]\frac{1}{n}[/math], вероятность же какой-то последовательности чисел до n-ого элемента при известном [math]a_{n}[/math] останется [math] \frac {1}{(k-1)!}[/math], что в результате дает, что вероятность всей перестановки [math] \frac {1}{k!}[/math]

Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за [math] n [/math] шагов, таким образом автоматически получается, что все [math] n![/math] перестановок равновероятны.

Неправильные способы реализации

Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например следующие два алгоритма работают неправильно:

 for i = 1..n
   swap(i, random(1..n))

 for i = 1..n
   swap(random(1..n), random(1..n))

В самом деле: в первом случае число способов сгенерировать последовательность в первом случае равно [math]n^n[/math], во втором равно [math] (n^2)^n[/math], а всего последовательностей [math] n![/math]. Для того, чтобы сгенерированная последовательность была случайной, необходимо хотя бы, чтобы число способов получить последовательность было кратно их общему числу. То есть в первом случае необходимо [math](n^n) \vdots n![/math] а во втором случае [math]((n^2)^n) \vdots n![/math], что заведомо не выполняется при подстановке любого нечетного числа, начиная с 3.

Примечание

• Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Ятс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).
  
• Нетрудно увидеть, что сложность алгоритма [math] O(n)[/math]

Литература

• Дональд Кнут Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2