Теория
Перемешивание переставляет элементы списка в случайном порядке. Честный способ — алгоритм Фишера–Йетса: пройти список с конца, на каждом шаге выбрать случайный элемент из ещё не обработанной части и обменять с текущим. Каждая из \(n!\) перестановок получается равновероятно.
Наивный способ — назначить каждому элементу случайное число и отсортировать — почти честен, но даёт едва заметный перекос. Перемешивание используют для жеребьёвки, случайных выборок и игр.
Важно: перемешивание случайно, поэтому результат не обязан отличаться от исходного порядка — совпадение иногда случается.
Пример с решением
- Условие. Перемешайте список «А, Б, В, Г».
- Формула. Фишер–Йетс: с конца списка обмениваем элементы со случайными.
- Подстановка. Четыре элемента — 24 возможные перестановки.
- Вычисление. Пример результата: «В, А, Г, Б» — одна из равновероятных.
- Ответ. Перемешанный список; каждый запуск даёт другую перестановку. Калькулятор с этим списком вернёт случайный порядок элементов.
Главное
- Фишер–Йетс — честное перемешивание.
- Все \(n!\) перестановок равновероятны.
- Результат случаен — повторы допустимы.