223
правки
Изменения
Нет описания правки
swap(i, random(1..i))
Этот алгоритм носит имя Фишера-Йетса.
==Обоснование==
Проведем его по индукции. Требуется доказать, что на каждом шаге цикла каждая перестановка равновероятна.
*Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Ятс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).<br/>
*Нетрудно увидеть, что сложность алгоритма <tex> O(n)</tex>
==Литература==
*Дональд Кнут Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
