Amestecător de Liste Aleatorii - Instrument Gratuit de Randomizare a Listelor

Ce este un instrument de amestecare aleatorie a listelor?

Un instrument de amestecare aleatorie a listelor preia o listă de elemente și o reordonează aleatoriu. Introduceți nume, sarcini sau orice altceva, câte un element pe linie, iar instrumentul le rearanjează astfel încât fiecare ordine posibilă să aibă aceeași probabilitate de apariție. Acest instrument folosește amestecarea Fisher–Yates, un algoritm bine cunoscut pentru generarea unor ordini aleatorii fără distorsiuni.

Cum se folosește instrumentul de amestecare aleatorie a listelor

1. Introduceți sau lipiți lista în casetă, câte un element pe linie.
2. Faceți clic pe „Randomize List”. Elementele se rearanjează instantaneu.
3. Citiți lista amestecată de sub buton, numerotată în noua ordine.
4. Faceți din nou clic pe „Randomize List” pentru o nouă amestecare independentă.
5. Faceți clic pe „Copy Result” pentru a copia noua ordine sau pe „Clear” pentru a o lua de la capăt.

Liniile goale din datele introduse sunt eliminate automat, astfel încât întreruperile suplimentare de linie nu vor crea elemente goale în rezultate.

Cum funcționează algoritmul de amestecare Fisher-Yates?

Amestecarea Fisher–Yates parcurge lista o singură dată, începând cu ultimul element și înaintând spre primul. La fiecare pas, alege aleatoriu un element din partea listei care nu a fost încă plasată și îl schimbă cu elementul aflat pe poziția curentă.

Formula amestecării Fisher-Yates

Pentru o listă cu n elemente, numerotate de la poziția 0 până la poziția 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

Bucla rulează de n − 1 ori, astfel încât amestecarea necesită în total aproximativ n pași. Acesta se numește timp liniar și se notează O(n). Deoarece algoritmul ia în considerare fiecare poziție exact o dată și alege dintr-un set de elemente care se micșorează și este bine definit, fiecare dintre cele n! (n factorial: n × (n − 1) × ... × 1) de ordini posibile are aceeași probabilitate de a fi rezultatul.

Exemplu: amestecarea unei liste cu patru elemente

Se pornește cu patru elemente pe pozițiile 0 până la 3: Măr, Banană, Cireașă, Curmală.

• i = 3: alegerea aleatorie este j = 0. Se schimbă pozițiile 3 și 0 → Curmală, Banană, Cireașă, Măr
• i = 2: alegerea aleatorie este j = 2. Schimbarea unui element cu el însuși nu modifică nimic → Curmală, Banană, Cireașă, Măr
• i = 1: alegerea aleatorie este j = 0. Se schimbă pozițiile 1 și 0 → Banană, Curmală, Cireașă, Măr

Ordinea finală: Banană, Curmală, Cireașă, Măr.

Pentru patru elemente există 4! = 24 ordini posibile. Fiecare dintre ele, inclusiv aceasta, are o șansă de 1 la 24 să apară la orice amestecare.

De ce să nu schimbăm pur și simplu perechi aleatorii?

O metodă aparent mai simplă — alegerea a două poziții aleatorii și schimbarea lor, repetată de mai multe ori — pare aleatorie, dar nu este. Unele programe timpurii de amestecare din anii 1950 funcționau astfel și favorizau discret anumite ordini în detrimentul altora, chiar dacă nicio rulare individuală nu părea suspectă. Amestecarea Fisher–Yates evită acest lucru deoarece fiecare element este mutat exact o dată, pe o poziție aleasă dintr-un set de opțiuni care se micșorează cu precizie; astfel, fiecare ordine finală este la fel de probabilă.

De unde provine amestecarea Fisher-Yates?

Statisticienii Ronald Fisher și Frank Yates au descris metoda în 1938, într-o carte de tabele statistice, pentru amestecarea manuală în procesul de proiectare a experimentelor. În 1964, Richard Durstenfeld a adaptat-o pentru calculatoare, astfel încât o listă să poată fi reordonată pe loc, fără a fi nevoie de o a doua listă pentru evidența elementelor rămase. Donald Knuth a inclus această versiune pentru calculatoare în cartea sa din 1969, Arta programării calculatoarelor, motiv pentru care este numită uneori amestecarea Knuth. Browserele web folosesc astăzi același algoritm.

Utilizări frecvente ale unui instrument de amestecare a listelor

• Stabilirea ordinii în care elevii prezintă sau răspund la întrebări la clasă
• Stabilirea participanților într-o schemă de turneu sau a ordinii turelor într-un joc
• Împărțirea unui grup în echipe aleatorii
• Alegerea unui restaurant, a unui film sau a unei sarcini dintr-o listă scurtă, fără a favoriza o opțiune

O amestecare simplă nu este întotdeauna potrivită. Dacă unele elemente trebuie să apară mai des decât altele, selecția ponderată este mai adecvată. Dacă este necesar ca fiecare categorie să fie reprezentată, eșantionarea stratificată funcționează mai bine decât o singură amestecare aleatorie.

Întrebări frecvente

Este amestecarea cu adevărat aleatorie?

Aceasta se bazează pe generatorul de numere pseudoaleatoare (PRNG) al browserului web, o formulă care produce secvențe de numere ce se comportă ca aleatorii în scopuri practice. Este suficient pentru ordinea prezentărilor la clasă, stabilirea tabloului unui turneu sau alegerea unui film. Nu este destinat criptografiei, sistemelor de jocuri de noroc sau oricărei situații în care banii ori securitatea depind de imprevizibilitate; pentru acestea sunt necesari generatori de numere aleatoare certificați.

Instrumentul trimite lista mea către un server?

Amestecarea propriu-zisă se execută integral în browser, folosind JavaScript, astfel încât nu este necesară nicio solicitare de rețea pentru reordonarea listei. Lista curentă este scrisă și în adresa web a paginii, astfel încât o reîncărcare sau un marcaj nu o pierde. Dacă adresa este copiată, partajată sau redeschisă, lista este transmisă împreună cu aceasta, inclusiv către orice server care încarcă ulterior pagina. Evitați să introduceți informații sensibile în listă dacă acest aspect este important.

Ce se întâmplă cu elementele duplicate?

Elementele duplicate sunt păstrate. Dacă „Sam” apare de două ori în datele introduse, va apărea tot de două ori în rezultatul amestecat, posibil pe poziții diferite.

Există o limită pentru numărul de elemente care pot fi amestecate?

Instrumentul nu are o limită prestabilită. Deoarece amestecarea se execută în timp liniar, chiar și listele lungi sunt reordonate într-o fracțiune de secundă pe orice dispozitiv modern.

Prin ce diferă amestecarea de sortare?

Sortarea aranjează elementele după o regulă fixă, cum ar fi ordinea alfabetică, și produce întotdeauna același rezultat pentru aceleași date de intrare. Amestecarea aranjează elementele aleatoriu și produce aproape de fiecare dată o ordine diferită, chiar și atunci când datele de intrare sunt identice.

Pot amesteca aceeași listă de mai multe ori?

Da. Fiecare clic pe „Randomize List” execută din nou algoritmul, independent de orice amestecare anterioară. Pentru o listă mică, o ordine repetată este posibilă din întâmplare; pentru o listă mai mare, devine extrem de improbabilă.