Перемешиватель случайных списков - бесплатный онлайн инструмент для случайного упорядочивания

Что такое перемешиватель случайного списка?

Перемешиватель случайного списка — это инструмент, который принимает список элементов и возвращает его в новом случайном порядке. Введите имена, задачи или любые другие элементы, по одному в строке, и инструмент переставит их так, чтобы у каждого возможного порядка был одинаковый шанс появиться. Этот инструмент использует алгоритм перемешивания Фишера—Йетса — хорошо известный алгоритм получения равновероятных случайных перестановок.

Как пользоваться перемешивателем случайного списка

1. Введите или вставьте список в поле, по одному элементу в строке.
2. Нажмите «Randomize List». Элементы будут мгновенно переставлены.
3. Прочитайте перемешанный список под кнопкой: элементы будут пронумерованы в новом порядке.
4. Нажмите «Randomize List» ещё раз, чтобы выполнить новое независимое перемешивание.
5. Нажмите «Copy Result», чтобы скопировать новый порядок, или «Clear», чтобы начать заново.

Пустые строки во введённых данных удаляются автоматически, поэтому дополнительные переводы строк не создадут пустых элементов в результатах.

Как работает алгоритм перемешивания Фишера—Йетса?

Перемешивание Фишера—Йетса проходит по списку один раз, начиная с последнего элемента и двигаясь к началу. На каждом шаге алгоритм случайно выбирает один элемент из ещё не размещённой части списка и меняет его местами с элементом на текущей позиции.

Формула перемешивания Фишера—Йетса

Для списка из n элементов, пронумерованных от позиции 0 до позиции n − 1:

1for i from n − 1 down to 1:
2    choose a random whole number j, where 0 ≤ j ≤ i
3    swap the items at positions i and j
4

Цикл выполняется n − 1 раз, поэтому перемешивание в общей сложности занимает около n шагов. Это называется линейным временем и записывается как O(n). Поскольку алгоритм рассматривает каждую позицию ровно один раз и выбирает элементы из постепенно уменьшающегося, чётко определённого множества, каждый из n! (факториал n: n × (n − 1) × ... × 1) возможных порядков имеет одинаковую вероятность стать результатом.

Пример: перемешивание списка из четырёх элементов

Начнём с четырёх элементов на позициях от 0 до 3: яблоко, банан, вишня, финик.

• i = 3: случайно выбранная позиция — j = 0. Меняем местами позиции 3 и 0 → финик, банан, вишня, яблоко
• i = 2: случайно выбранная позиция — j = 2. Обмен элемента с самим собой ничего не меняет → финик, банан, вишня, яблоко
• i = 1: случайно выбранная позиция — j = 0. Меняем местами позиции 1 и 0 → банан, финик, вишня, яблоко

Итоговый порядок: банан, финик, вишня, яблоко.

Для четырёх элементов существует 4! = 24 возможных порядков. Каждый из них, включая этот, имеет шанс 1 из 24 появиться при любом отдельном перемешивании.

Почему бы просто не менять местами случайные пары?

Более простой на вид метод — выбирать две случайные позиции и менять их местами, повторяя это несколько раз, — выглядит случайным, но таковым не является. Некоторые первые программы для перемешивания из 1950-х работали именно так и незаметно отдавали предпочтение одним порядкам перед другими, хотя отдельный запуск не выглядел подозрительно. Перемешивание Фишера—Йетса этого избегает: каждый элемент перемещается ровно один раз на позицию, выбранную из точно определённого, постепенно уменьшающегося множества вариантов, поэтому каждый итоговый порядок имеет одинаковую вероятность.

Откуда появилось перемешивание Фишера—Йетса?

Статистики Рональд Фишер и Фрэнк Йетс описали этот метод в 1938 году в книге статистических таблиц для ручного перемешивания при планировании экспериментов. В 1964 году Ричард Дёрстенфельд адаптировал его для компьютеров, чтобы список можно было переставлять на месте, без второго списка для отслеживания оставшихся элементов. Дональд Кнут включил эту компьютерную версию в свою книгу Искусство программирования, опубликованную в 1969 году, поэтому иногда её называют перемешиванием Кнута. Сегодня веб-браузеры используют тот же алгоритм.

Распространённые случаи использования перемешивателя списка

• Определение порядка, в котором учащиеся выступают или отвечают на вопросы в классе
• Формирование сетки турнира или определение очерёдности ходов в игре
• Случайное разделение группы на команды
• Выбор ресторана, фильма или задачи из короткого списка без предпочтения одного варианта перед другими

Обычное перемешивание подходит не всегда. Если некоторые элементы должны появляться чаще других, лучше использовать взвешенный выбор. Если необходимо гарантированно представить каждую категорию, стратифицированная выборка подходит лучше, чем одно случайное перемешивание.

Часто задаваемые вопросы

Действительно ли перемешивание случайно?

Он использует генератор псевдослучайных чисел (PRNG) веб-браузера — формулу, создающую последовательности чисел, которые на практике ведут себя как случайные. Этого достаточно для составления порядка выступлений в классе, жеребьёвки участников турнира или выбора фильма. Такой генератор не предназначен для криптографии, азартных игр или любых задач, где непредсказуемость связана с деньгами или безопасностью; для них нужны сертифицированные генераторы случайных чисел.

Отправляет ли инструмент мой список на сервер?

Само перемешивание полностью выполняется в браузере с помощью JavaScript, поэтому для перестановки списка сетевой запрос не нужен. Текущий список также записывается в адрес веб-страницы, поэтому после перезагрузки или добавления страницы в закладки он не теряется. Если этот адрес скопировать, передать кому-либо или открыть снова, список будет содержаться в нём и попадёт в том числе на любой сервер, который впоследствии загрузит эту страницу. Если это имеет значение, не помещайте в список конфиденциальные сведения.

Что происходит с одинаковыми элементами?

Одинаковые элементы сохраняются. Если «Sam» встречается во введённых данных дважды, в перемешанном результате он также появится дважды, возможно, на разных позициях.

Есть ли ограничение на количество перемешиваемых элементов?

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

Чем перемешивание отличается от сортировки?

Сортировка располагает элементы по фиксированному правилу, например в алфавитном порядке, и для одинаковых входных данных всегда даёт один и тот же результат. Перемешивание располагает элементы случайным образом и почти каждый раз создаёт новый порядок, даже если входные данные идентичны.

Можно ли перемешать один и тот же список несколько раз?

Да. Каждое нажатие «Randomize List» снова запускает алгоритм независимо от предыдущих перемешиваний. Для небольшого списка одинаковый порядок может случайно повториться; для большого списка это становится крайне маловероятным.