Генератор випадкового списку - безкоштовний онлайн-інструмент для перемішування списків

Що таке перемішувач списку?

Перемішувач списку — це інструмент, який бере список елементів і розташовує їх у новому випадковому порядку. Введіть імена, завдання чи будь-що інше, по одному елементу в рядку, і інструмент переставить їх так, щоб кожен можливий порядок мав однакову ймовірність. Цей інструмент використовує алгоритм перемішування Фішера—Єйтса — відомий алгоритм отримання неупереджених випадкових перестановок.

Як користуватися перемішувачем списку

1. Введіть або вставте список у поле, по одному елементу в рядку.
2. Натисніть «Рандомізувати список». Елементи буде миттєво переставлено.
3. Прочитайте перемішаний список під кнопкою, пронумерований у новому порядку.
4. Натисніть «Рандомізувати список» ще раз, щоб виконати нове незалежне перемішування.
5. Натисніть «Копіювати результат», щоб скопіювати новий порядок, або «Очистити», щоб почати спочатку.

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

Як працює алгоритм перемішування Фішера—Єйтса?

Перемішування Фішера—Єйтса проходить список один раз, починаючи з останнього елемента й рухаючись до початку. На кожному кроці він випадково вибирає один елемент із частини списку, яку ще не було розміщено, і міняє його місцями з елементом на поточній позиції.

Формула перемішування Фішера—Єйтса

Для списку з 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: Apple, Banana, Cherry, Date.

• i = 3: випадково вибрано j = 0. Поміняємо місцями позиції 3 і 0 → Date, Banana, Cherry, Apple
• i = 2: випадково вибрано j = 2. Обмін позиції із самою собою нічого не змінює → Date, Banana, Cherry, Apple
• i = 1: випадково вибрано j = 0. Поміняємо місцями позиції 1 і 0 → Banana, Date, Cherry, Apple

Кінцевий порядок: Banana, Date, Cherry, Apple.

Для чотирьох елементів існує 4! = 24 можливих порядків. Кожен із них, зокрема цей, має шанс 1 із 24 випасти під час будь-якого перемішування.

Чому б просто не міняти місцями випадкові пари?

Простіший на вигляд метод — вибирати дві випадкові позиції та міняти їх місцями, повторюючи це кілька разів, — здається випадковим, але таким не є. Деякі ранні програми для перемішування з 1950-х працювали саме так і непомітно надавали перевагу одним порядкам перед іншими, хоча жоден окремий запуск не виглядав підозріло. Перемішування Фішера—Єйтса цього уникає, оскільки кожен елемент переміщується рівно один раз у позицію, вибрану з точно визначеного набору варіантів, який поступово скорочується. Саме тому кожен кінцевий порядок має однакову ймовірність.

Звідки походить перемішування Фішера—Єйтса?

Статистики Рональд Фішер і Френк Єйтс описали цей метод у 1938 році в книзі статистичних таблиць для ручного перемішування під час планування експериментів. У 1964 році Річард Дурстенфельд адаптував його для комп’ютерів, щоб список можна було переставляти на місці без другого списку для відстеження елементів, що залишилися. Дональд Кнут включив цю комп’ютерну версію до своєї книги Мистецтво програмування, опублікованої 1969 року, через що її іноді називають перемішуванням Кнута. Сьогодні веббраузери використовують той самий алгоритм.

Поширені способи використання перемішувача списку

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

Просте перемішування підходить не завжди. Якщо деякі елементи мають з’являтися частіше за інші, краще використовувати зважений вибір. Якщо кожна категорія має бути гарантовано представлена, стратифікована вибірка підходить краще, ніж одне випадкове перемішування.

Поширені запитання

Чи справді перемішування є випадковим?

Воно використовує генератор псевдовипадкових чисел (PRNG) веббраузера — формулу, яка створює послідовності чисел, що на практиці поводяться як випадкові. Цього достатньо для визначення порядку виступів у класі, формування сітки турніру чи вибору фільму. Такий генератор не призначений для криптографії, азартних ігор або будь-яких випадків, де від непередбачуваності залежать гроші чи безпека; для цього потрібні сертифіковані генератори випадкових чисел.

Чи надсилає інструмент мій список на сервер?

Саме перемішування повністю виконується у веббраузері за допомогою JavaScript, тому для переставлення списку мережевий запит не потрібен. Поточний список також записується у вебадресу сторінки, тому після перезавантаження або відкриття закладки він не втрачається. Якщо цю адресу скопіювати, поширити або відкрити знову, список передається разом із нею, зокрема на будь-який сервер, який згодом завантажує цю сторінку. Якщо це важливо, не додавайте до списку конфіденційні дані.

Що відбувається з однаковими елементами?

Однакові елементи зберігаються. Якщо «Sam» двічі введено у список, він і в перемішаному результаті з’явиться двічі, можливо на різних позиціях.

Чи є обмеження на кількість елементів, які можна перемішати?

Інструмент не має вбудованого обмеження. Оскільки перемішування виконується за лінійний час, навіть довгі списки переставляються за частки секунди на будь-якому сучасному пристрої.

Чим перемішування відрізняється від сортування?

Сортування розташовує елементи за фіксованим правилом, наприклад в алфавітному порядку, і для однакових вхідних даних завжди дає той самий результат. Перемішування розташовує елементи випадково й майже щоразу створює інший порядок, навіть для ідентичних вхідних даних.

Чи можна перемішати той самий список більше одного разу?

Так. Кожне натискання «Рандомізувати список» знову запускає алгоритм незалежно від попереднього перемішування. Для невеликого списку повторення порядку можливе випадково; для більшого списку воно стає вкрай малоймовірним.