Метод генерации случайной перестановки, алгоритм Фишера-Йетса
Тасование Фишера–Йетса (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) – алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Основная процедура тасования Фишера–Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.
Содержание
Постановка задачи
Необходимо сгенерировать случайную перестановку из
чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.Решение
Пусть
Следующий алгоритм решает задачу:
int *a randomPermutation(int *a) // *a - указатель на массив типа int длины n for i = 1 to n j = random(1..i) swap(a[i], a[j]) return a
Обоснование
Проведем доказательство по индукции. Всего перестановок
, поэтому вероятность каждой из них должна быть равна . Показажем, что на каждом -ом шаге цикла любая перестановка из первых элементов равновероятна.- при перестановка всего одна, и, очевидно, что база верна
- пусть при каждая перестановка первых элементов равновероятна, то есть вероятность каждой отдельно взятой перестановки на -ом шаге цикла равна
- при :
- после вероятность какого-то числа оказаться на -ом месте равна . Вероятность же какой-то перестановки первых элементов при известном останется , что в результате дает, что вероятность перестановки первых элементов равна
Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за
шагов, таким образом автоматически получается, что все перестановок равновероятны.
Неправильные способы реализации
Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например, следующие два алгоритма работают неправильно:
for i = 1 to n swap(i, random(1..n))
for i = 1 to n swap(random(1..n), random(1..n))
В самом деле: число способов сгенерировать последовательность в первом случае равно
, в то время как существует всего возможных перестановок из элементов. Поскольку никогда не может делиться на без остатка при (так как делится на число , которое не имеет с общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие. Аналогично для второго случая, где число способов сгенерировать последовательность равно уже .Примечание
- Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Йетс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).
- Нетрудно увидеть, что сложность алгоритма
См.также
Источники информации
- Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
- Википедия - Тасование Фишера–Йетса
- Wikipedia - Fisher-Yates shuffle