Мешач случајних листи - Бесплатни онлајн алат за насумично распоређивање листи

Шта је насумични мешач списка?

Насумични мешач списка је алатка која узима списак ставки и враћа их у новом, насумичном редоследу. Унесите имена, задатке или било шта друго, по једну ставку у ред, а алатка ће их преуредити тако да сваки могући редослед има једнаку вероватноћу. Ова алатка користи Фишер–Јејтсов алгоритам мешања, познат алгоритам за добијање непристрасних насумичних редоследа.

Како се користи насумични мешач списка

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: јабука, банана, трешња, урма.

• 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-а, па за преуређивање списка није потребан мрежни захтев. Тренутни списак се такође уписује у веб-адресу странице, па се поновним учитавањем или обележивачем не губи. Ако се та адреса копира, пошаље другима или поново отвори, списак путује са њом, укључујући и серверу који касније учита страницу. Ако је то важно, немојте у списак стављати осетљиве информације.

Шта се дешава са дуплираним ставкама?

Дупликати се задржавају. Ако се „Сам“ у уносу појави два пута, и у измешаном резултату ће се појавити два пута, можда на различитим позицијама.

Да ли постоји ограничење броја ставки које могу да измешам?

Алатка нема уграђено ограничење. Пошто се мешање извршава у линеарном времену, чак се и дуги спискови на сваком савременом уређају преуреде за делић секунде.

По чему се мешање разликује од сортирања?

Сортирање ређа ставке према утврђеном правилу, као што је азбучни ред, и за исти унос увек даје исти резултат. Мешање ређа ставке насумично и скоро сваки пут даје другачији редослед, чак и када је унос исти.

Могу ли исти списак да измешам више пута?

Да. Сваки клик на „Насумично измешај списак“ поново покреће алгоритам, независно од сваког претходног мешања. Код малог списка поновљени редослед може да се појави случајно; код већег списка то постаје изузетно мало вероватно.