Losowy Mieszacz List - Darmowe Narzędzie do Losowego Porządkowania List

Czym jest losowe tasowanie listy?

Narzędzie do losowego tasowania listy przyjmuje listę elementów i układa je ponownie w nowej, losowej kolejności. Wpisz imiona, zadania lub cokolwiek innego, każdy element w osobnym wierszu, a narzędzie je przestawi, tak aby każda możliwa kolejność miała jednakową szansę wystąpienia. Narzędzie korzysta z algorytmu tasowania Fishera–Yatesa, dobrze znanej metody tworzenia bezstronnie losowych kolejności.

Jak korzystać z losowego tasowania listy

1. Wpisz lub wklej listę w polu, po jednym elemencie w wierszu.
2. Kliknij „Losuj listę”. Elementy zostaną natychmiast przestawione.
3. Odczytaj przetasowaną listę pod przyciskiem, ponumerowaną w nowej kolejności.
4. Kliknij ponownie „Losuj listę”, aby wykonać nowe, niezależne tasowanie.
5. Kliknij „Kopiuj wynik”, aby skopiować nową kolejność, albo „Wyczyść”, aby rozpocząć od nowa.

Puste wiersze w danych wejściowych są automatycznie usuwane, więc dodatkowe podziały wiersza nie spowodują pojawienia się pustych elementów w wynikach.

Jak działa algorytm tasowania Fishera–Yatesa?

Tasowanie Fishera–Yatesa przechodzi przez listę jeden raz, zaczynając od ostatniego elementu i kierując się ku początkowi. Na każdym etapie losowo wybiera jeden element z nieumieszczonej jeszcze części listy i zamienia go z elementem znajdującym się na bieżącej pozycji.

Wzór tasowania Fishera–Yatesa

Dla listy n elementów, ponumerowanych od pozycji 0 do pozycji 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

Pętla wykonuje n − 1 iteracji, więc tasowanie zajmuje łącznie około n kroków. Nazywa się to czasem liniowym i zapisuje jako O(n). Ponieważ algorytm rozpatruje każdą pozycję dokładnie raz i za każdym razem wybiera element z coraz mniejszego, jasno określonego zbioru, każda z n! możliwych kolejności (silnia n: n × (n − 1) × ... × 1) ma jednakową szansę stać się wynikiem.

Przykład: tasowanie listy czterech elementów

Zacznijmy od czterech elementów na pozycjach od 0 do 3: jabłko, banan, wiśnia, daktyl.

• i = 3: wylosowano j = 0. Zamień pozycje 3 i 0 → daktyl, banan, wiśnia, jabłko
• i = 2: wylosowano j = 2. Zamiana pozycji z samą sobą niczego nie zmienia → daktyl, banan, wiśnia, jabłko
• i = 1: wylosowano j = 0. Zamień pozycje 1 i 0 → banan, daktyl, wiśnia, jabłko

Ostateczna kolejność: banan, daktyl, wiśnia, jabłko.

Dla czterech elementów istnieje 4! = 24 możliwych kolejności. Każda z nich, w tym ta, ma przy każdym tasowaniu szansę wynoszącą 1 na 24.

Dlaczego nie zamieniać po prostu losowych par?

Prostsza na pozór metoda — wybieranie dwóch losowych pozycji i zamienianie ich, powtarzane kilka razy — wygląda losowo, ale taka nie jest. Niektóre z pierwszych programów do tasowania, powstałe w latach 1950, działały w ten sposób i niepostrzeżenie faworyzowały pewne kolejności kosztem innych, mimo że pojedyncze wykonanie nie wyglądało podejrzanie. Tasowanie Fishera–Yatesa unika tego problemu, ponieważ każdy element jest przenoszony dokładnie raz na pozycję wybraną z precyzyjnie kurczącego się zbioru możliwości. Dzięki temu każda końcowa kolejność jest równie prawdopodobna.

Skąd pochodzi tasowanie Fishera–Yatesa?

Statystycy Ronald Fisher i Frank Yates opisali tę metodę w 1938 roku w książce z tablicami statystycznymi, jako sposób ręcznego tasowania przy projektowaniu eksperymentów. W 1964 roku Richard Durstenfeld przystosował ją do komputerów, aby listę można było porządkować w miejscu, bez potrzeby używania drugiej listy do śledzenia pozostałych elementów. Donald Knuth zamieścił tę komputerową wersję w swojej książce Sztuka programowania, wydanej w 1969 roku, dlatego metoda ta bywa nazywana tasowaniem Knutha. Obecnie tej samej metody używają przeglądarki internetowe.

Typowe zastosowania narzędzia do tasowania listy

• Ustalanie kolejności, w której uczniowie prezentują materiały lub odpowiadają na pytania w klasie
• Ustalanie rozstawienia w turnieju lub kolejności wykonywania ruchów w grze
• Losowy podział grupy na zespoły
• Wybieranie restauracji, filmu lub zadania z krótkiej listy bez faworyzowania żadnej opcji

Zwykłe tasowanie nie zawsze jest odpowiednim rozwiązaniem. Jeśli niektóre elementy powinny pojawiać się częściej niż inne, lepiej sprawdzi się losowanie ważone. Jeśli każda kategoria musi być reprezentowana, losowanie warstwowe sprawdzi się lepiej niż pojedyncze losowe tasowanie.

Często zadawane pytania

Czy tasowanie jest naprawdę losowe?

Opiera się ono na generatorze liczb pseudolosowych (PRNG) przeglądarki internetowej — wzorze, który tworzy ciągi liczb zachowujące się jak losowe do celów praktycznych. To wystarcza do ustalania kolejności w klasie, rozstawienia uczestników w turnieju lub wybierania filmu. Nie nadaje się on do zastosowań w kryptografii, systemach hazardowych ani w sytuacjach, w których pieniądze lub bezpieczeństwo zależą od nieprzewidywalności; do takich celów potrzebne są certyfikowane generatory liczb losowych.

Czy narzędzie wysyła moją listę na serwer?

Samo tasowanie odbywa się w całości w przeglądarce za pomocą JavaScriptu, więc do przestawienia listy nie jest potrzebne żadne żądanie sieciowe. Bieżąca lista jest również zapisywana w adresie strony, więc jej ponowne załadowanie lub dodanie do zakładek nie powoduje jej utraty. Jeśli adres zostanie skopiowany, udostępniony lub ponownie otwarty, lista zostanie do niego dołączona, także na każdym serwerze, który później załaduje tę stronę. Jeśli ma to znaczenie, nie umieszczaj na liście poufnych informacji.

Co dzieje się z powtarzającymi się elementami?

Powtarzające się elementy pozostają na liście. Jeśli „Sam” pojawi się na wejściu dwa razy, w przetasowanym wyniku również pojawi się dwa razy, być może na różnych pozycjach.

Czy istnieje limit liczby elementów, które mogę przetasować?

Narzędzie nie ma wbudowanego limitu. Ponieważ tasowanie działa w czasie liniowym, nawet długie listy są przestawiane w ułamku sekundy na każdym współczesnym urządzeniu.

Czym tasowanie różni się od sortowania?

Sortowanie układa elementy według ustalonej reguły, na przykład alfabetycznie, i zawsze daje ten sam wynik dla tych samych danych wejściowych. Tasowanie układa elementy losowo i niemal za każdym razem daje inną kolejność, nawet przy identycznych danych wejściowych.

Czy mogę tasować tę samą listę więcej niż raz?

Tak. Każde kliknięcie „Losuj listę” uruchamia algorytm ponownie, niezależnie od wcześniejszego tasowania. W przypadku małej listy powtórzenie kolejności może się zdarzyć losowo; przy większej liście staje się skrajnie mało prawdopodobne.