Разбъркване на случаен списък - Безплатен онлайн инструмент за разбъркване на списъци

Какво представлява инструментът за случайно разбъркване на списъци?

Инструментът за случайно разбъркване на списъци приема списък с елементи и ги подрежда отново в нов, случаен ред. Въведете имена, задачи или каквото и да е друго, по един елемент на ред, и инструментът ще ги пренареди така, че всеки възможен ред да има еднакъв шанс да се получи. Инструментът използва разбъркването на Фишер–Йейтс — добре познат алгоритъм за създаване на безпристрастни случайни подреждания.

Как се използва инструментът за случайно разбъркване на списъци

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, така че за пренареждането на списъка не е необходима мрежова заявка. Текущият списък се записва и в уеб адреса на страницата, така че презареждането или добавянето на отметка не го губи. Ако този адрес бъде копиран, споделен или отворен отново, списъкът пътува с него, включително до всеки сървър, който по-късно зареди страницата. Ако това е от значение, не поставяйте чувствителна информация в списъка.

Какво се случва с повтарящите се елементи?

Повтарящите се елементи се запазват. Ако „Сам“ се появява два пъти във входните данни, той ще се появи два пъти и в разбъркания резултат, вероятно на различни позиции.

Има ли ограничение за броя елементи, които мога да разбъркам?

В инструмента няма вградено ограничение. Тъй като разбъркването се изпълнява за линейно време, дори дълги списъци се пренареждат за част от секундата на всяко съвременно устройство.

По какво разбъркването се различава от сортирането?

Сортирането подрежда елементите по фиксирано правило, например по азбучен ред, и винаги дава един и същ резултат при едни и същи входни данни. Разбъркването подрежда елементите на случаен принцип и почти всеки път дава различен ред, дори при еднакви входни данни.

Мога ли да разбъркам един и същ списък повече от веднъж?

Да. При всяко натискане на „Случайно разбъркване на списъка“ алгоритъмът се изпълнява отново, независимо от всички предишни разбърквания. При малък списък е възможно по случайност да се повтори същият ред; при по-голям списък това става изключително малко вероятно.