Barrejador Aleatori de Llistes - Eina Gratuïta de Reordenació Aleatòria

Què és un aleatoritzador de llistes?

Un aleatoritzador de llistes és una eina que agafa una llista d’elements i els torna a col·locar en un ordre nou i aleatori. Escriviu-hi noms, tasques o qualsevol altra cosa, una per línia, i l’eina els reorganitza de manera que tots els ordres possibles tinguin la mateixa probabilitat d’aparèixer. Aquesta eina utilitza la barreja de Fisher-Yates, un algorisme conegut per generar ordres aleatoris no esbiaixats.

Com s’utilitza el desordenador aleatori de llistes

1. Escriviu o enganxeu la llista al quadre, un element per línia.
2. Feu clic a «Randomize List». Els elements es reorganitzen immediatament.
3. Llegiu la llista desordenada sota del botó, numerada en el seu ordre nou.
4. Feu clic de nou a «Randomize List» per fer una nova permutació independent.
5. Feu clic a «Copy Result» per copiar l’ordre nou, o a «Clear» per començar de nou.

Les línies en blanc de l’entrada s’eliminen automàticament, de manera que els salts de línia addicionals no creen entrades buides als resultats.

Com funciona l’algorisme de permutació de Fisher-Yates?

La barreja de Fisher-Yates recorre la llista una vegada, començant per l’últim element i avançant cap al principi. En cada pas, tria aleatòriament un element de la part de la llista que encara no s’ha col·locat i l’intercanvia amb l’element que ocupa la posició actual.

Fórmula de la permutació de Fisher-Yates

Per a una llista de n elements, numerats des de la posició 0 fins a la posició 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

El bucle s’executa n − 1 vegades, de manera que la permutació tarda aproximadament n passos en total. Això s’anomena temps lineal i s’escriu O(n). Com que l’algorisme considera cada posició exactament una vegada i extreu elements d’un conjunt de possibilitats que es redueix de manera ben definida, cadascuna de les n! (factorial de n: n × (n − 1) × ... × 1) ordenacions possibles té la mateixa probabilitat de ser el resultat.

Exemple: barrejar una llista de quatre elements

Comenceu amb quatre elements a les posicions 0 a 3: Apple, Banana, Cherry, Date.

• i = 3: l’elecció aleatòria és j = 0. Canvieu les posicions 3 i 0 → Date, Banana, Cherry, Apple
• i = 2: l’elecció aleatòria és j = 2. Canviar una posició amb ella mateixa no modifica res → Date, Banana, Cherry, Apple
• i = 1: l’elecció aleatòria és j = 0. Canvieu les posicions 1 i 0 → Banana, Date, Cherry, Apple

Ordre final: Banana, Date, Cherry, Apple.

Amb quatre elements hi ha 4! = 24 ordres possibles. Cadascun, inclòs aquest, té una probabilitat de 1 entre 24 d’aparèixer en qualsevol permutació.

Per què no es poden intercanviar simplement parelles aleatòries?

Un mètode que sembla més senzill —triar dues posicions aleatòries i intercanviar-les, repetint-ho diverses vegades— sembla aleatori, però no ho és. Alguns dels primers programes de barreja, dels anys 1950, funcionaven així i afavorien discretament determinades ordenacions per damunt d’altres, encara que cap execució individual semblés sospitosa. La barreja de Fisher-Yates ho evita perquè cada element es mou exactament una vegada, a una posició extreta d’un conjunt de possibilitats que es redueix amb precisió; això fa que totes les ordenacions finals tinguin la mateixa probabilitat.

D’on prové la permutació de Fisher-Yates?

Els estadístics Ronald Fisher i Frank Yates van descriure el mètode l’any 1938 en un llibre de taules estadístiques, per barrejar elements manualment durant el disseny d’experiments. L’any 1964, Richard Durstenfeld el va adaptar per als ordinadors, de manera que una llista es pogués reordenar in situ, sense necessitat d’una segona llista per controlar què hi quedava. Donald Knuth va incloure aquesta versió informàtica al seu llibre de 1969 The Art of Computer Programming, motiu pel qual de vegades s’anomena barreja de Knuth. Actualment, els navegadors web utilitzen el mateix algorisme.

Usos habituals d’un aleatoritzador de llistes

• Establir l’ordre en què els estudiants fan presentacions o responen preguntes a classe
• Determinar els caps de sèrie d’un quadre de torneig o establir l’ordre dels torns en un joc
• Dividir un grup en equips aleatoris
• Triar un restaurant, una pel·lícula o una tasca d’una llista breu sense afavorir cap opció

Una barreja simple no sempre és l’opció adequada. Si cal que alguns elements apareguin més sovint que altres, la selecció ponderada s’hi adapta millor. Si cal garantir la representació de totes les categories, el mostreig estratificat funciona millor que una única barreja aleatòria.

Preguntes més freqüents

La barreja és realment aleatòria?

Depèn del generador de nombres pseudoaleatoris (PRNG) del navegador web, una fórmula que produeix seqüències de nombres que es comporten com si fossin aleatòries a efectes pràctics. Això és suficient per establir ordres a classe, determinar els caps de sèrie d’un torneig o triar una pel·lícula. No està dissenyat per a la criptografia, els sistemes d’apostes ni qualsevol situació en què els diners o la seguretat depenguin de la imprevisibilitat; en aquests casos calen generadors de nombres aleatoris certificats.

L’eina envia la meva llista a un servidor?

La barreja s’executa íntegrament al navegador mitjançant JavaScript, de manera que no cal cap sol·licitud de xarxa per reordenar la llista. La llista actual també s’escriu a l’adreça web de la pàgina, de manera que una recàrrega o un marcador no la fa desaparèixer. Si aquesta adreça es copia, es comparteix o es torna a obrir, la llista viatja amb ella, fins i tot al servidor que carregui posteriorment la pàgina. Si és rellevant, eviteu incloure informació sensible a la llista.

Què passa amb els elements duplicats?

Els duplicats es conserven. Si «Sam» apareix dues vegades a l’entrada, continuarà apareixent dues vegades a la sortida barrejada, possiblement en posicions diferents.

Hi ha un límit al nombre d’elements que puc desordenar?

L’eina no té cap límit incorporat. Com que la permutació s’executa en temps lineal, fins i tot les llistes llargues es reordenen en una fracció de segon en qualsevol dispositiu modern.

En què es diferencia barrejar de classificar?

La classificació ordena els elements segons una regla fixa, com ara l’ordre alfabètic, i sempre produeix el mateix resultat per a una mateixa entrada. La barreja col·loca els elements aleatòriament i produeix un ordre diferent gairebé cada vegada, fins i tot amb una entrada idèntica.

Puc barrejar la mateixa llista més d’una vegada?

Sí. Cada clic a «Randomize List» torna a executar l’algorisme, independentment de les barreges anteriors. Amb una llista petita, és possible que per atzar es repeteixi un ordre; amb una llista més gran, esdevé extremadament improbable.