Algoritme de Fisher-Yates

Representació gràfica de la versió de Durstenfeld de l'algoritme de Fisher-Yates per a mesclar un apany.

El algoritme de Fisher-Yates (o alguna variant del mateix) és un método per a barallar aleatoriamente una seqüència d'elements, garantisant que cada permutació tinga la mateixa provabilitat d'ocórrer. Funciona recorrent la llista, generalment d'arrere cap a avant, i en cada pas intercanvia l'element actual en un seleccionat aleatoriamente dels elements no vists fins a eixe moment. És un algoritme d'ordenament àmpliament utilisat per a generar mescles aleatòries de coleccions, com baralles de cartes o llistes de reproducció.

Història

L'algoritme Fisher-Yates apareix documentat per primera volta per Ronald A. Fisher i Frank Yates en el llibre Statistical tables for biological, agricultural and medical research. Si ben la seua descripció era realisada en llapis i paper, posteriorment atres autors –provablement sense coneiximent previ de dita publicació– varen elaborar el mateix algoritme. Lincoln E. Moses i Robert V. Oakford en Tables of Random Permutations i Durstenfeld en CACM-7 (1964), a els qui Knuth cita en el seu llibre The Art of Computer Programming i que descriu com a «Algoritme P» (pags. 139-140 del Vol.2).

En alguns països llatinoamericans, a este algoritme li'l coneix com el «barallat del capell», ya que la descripció que varen fer Fisher i Yates d'ell, és la que es porta a terme habitualment quan, –per eixemple–, es fa una rifa.

Transcripció a la programació

Va ser Durstenfeld qui primer va fer una transcripció en la forma d'algoritme per a usar-se en un ordenador. La descripció de Fisher i Yates exigix l'us de 2 matrius (en els treballs de camp, és simplement anotar en dos parts d'un paper, encara que be podria reutilisar-se borrant i rescribiendo en el mateix lloc), mentres que Durstenfeld usa la pròpia matriu per a portar a terme tot l'algoritme, necessitant solament com a memòria extra una variable temporal.

Descripció de l'algoritme

La forma més simple d'entendre-ho és partir de la forma popular:

• S'escriu cada número en un paperet doblat (construir el array), s'introduïxen tots els números en un capell, s'agita el contingut dins del capell (es barallen), després es van traent paperets que són disposts en el mateix orde en que es trauen, fins que no quede cap. El resultat és la llista barallada.
• La descripció (grosso modo) que donen Fisher i Yates és la següent: S'escriu en una llínea els números de l'orde de la série de 0 (o 1) fins al final de la série (se supon una série curta, manejable per mig de llapis i paper) i es dispon davall una atra llínea buida. I es fa lo següent:

1. S'elegix un a l'encert.
2. S'escriu en una atra llínea (a la dreta dels que ya haja escrits).
3. Es tacha de la llínea anterior (el número eixit a l'encert).

Es repetixen estos 3 passos, fins que solament quede 1, en la llínea de dalt sense tachar, llavors es pren directament i es passa a la d'avall.

• La descripció de Durstenfeld varia de la de Fisher i Yates, en que en portar-la a terme en un programa es tracta d'aforrar memòria i per tant tracta d'usar el mateix array, per a això, va intercanviant el valor de la posició a l'encert, i ho remplaza per l'últim del array no remplazado ya. És dir en iniciar l'algoritme, el primer elegit es remplaza per l'últim, en el següent cicle s'elegix a l'encert entre tots menys l'últim, que ara es remplaza pel penúltim, i de nou s'elegix un atre a l'encert entre tots menys els dos últims, etc. Bàsicament, Durstenfeld escriu el resultat a l'esquerra del previ, mentres que Fisher-Yates, ho feya a la dreta.

És un error comú pensar que la aleatorietat de la llista depén de l'algoritme de barallat (sempre que siga correcte, que per a cada posició siga elegida una posició a l'encert), quan en realitat depén de l'algoritme de aleatorietat/pseudoaleatorietat. La llista simplement és reordenada d'una atra manera: sempre conté els mateixos valors, solament canvien les seues posicions, que són depenents de l'algoritme de aleatorietat (que no s'està implementant, en cap cas). En qualsevol cas, una volta construït l'algoritme pot o deu provar-se el seu imparcialitat demostrant les desviacions de provabilitat.

Pseudocódigo de l'algoritme

Esta és la descripció de l'algoritme de Durstenfeld. Deu notar-se que l'element que queda al final del recorregut (ítem-0) com a entrada, és el primer en l'eixida, raó per la que no necessita ser intercanviat de posició (és la mateixa).

 Algoritme BarajadoAleatorio:
 Entrada:
      Un Array(0,1,2,3,4... Cantitat-1) de valors.
 Eixida:
      El mateix array en els seus valors en posicions aleatòries.
 Definició de variables:
      Cantitat: Un sancer que senyala la cantitat total de ítems que té el array.
      k: Un sancer, que rig el conte del bucle.
      az: Un sancer, elegit per una funció Random en el ranc 0-k (note's que k es va reduint).
      tmp: Un sancer, que ha de contindre un valor per a intercanviar valors entre 2 posicions.
 Funcions auxiliars:
      Tamany: Una funció que torna la cantitat d'elements que conté el array.
      Random: Una funció que torna un número aleatori d'un ranc de valors.
 
 Cantitat = Tamany(Array)  
 Recórrer en k des de Cantitat-1 fins a 1 Regresivamente
    az = Random(entre 0 i k)
         
    tmp = Array(az)
    Array(az) = Array(k)
    Array(k) = tmp
 Següent

Encara que el cost (en temps i memòria) siga major, el mateix algoritme tindria el següent pseudocódigo resolt en una estructura que permeta insercions i eliminacions en posicions arbitràries:

 Algoritme BarajadoAleatorio:
   Les variables són les mateixes del cas anterior, llevat, que en l'entrada en lloc d'un array,
   es rep una estructura (per eixemple una colecció, una llista enllaçada, un arbre, etc.)
 Recórrer en k des de Cantitat-1 fins a 1 Regresivamente
    az = Random(entre 0 i k)
         
    Estruc.AñadirItem(Estruc.Item(az), Al final)
    Estruc.BorrarItem(az)
 Següent

És interessant observar, en este cas, que els ítems en afegir-los al final, ho fan a la dreta de l'afegitó anterior, és dir tal com varen descriure Fisher i Yates. Si es preferix conservar un afegitó a l'esquerra del previ afegitó (tal com en el cas mostrat del array), deu canviar-se la llínea d'afegitó per la següent:

    Estruc.AñadirItem(Estruc.Item(az), En Posició k) 

ya que el bucle fa un recorregut regresivo, k val just 1 més de la posició llímit demanada a la funció Random, i s'afig just ans que siga eliminat l'element elegit, per tant k anirà sent sempre un valor menor en cada cicle, per lo que en efecte s'aniria colocant a l'esquerra del previ. Açò es pot vore més clar, en els eixemples passe a pas, en la secció corresponent (més avall).

Variants

• 1 L'algoritme, presenta algunes variants. De fet és prou fàcil que en tractar d'implementar dit algoritme s'acabe fent este atre. La particularitat Del qual més destacable, és que sempre que es baralla s'elegix de nou entre tots els existents (és com si el capell tinguera posicions a on es coloca cada u quan es fiquen, i despuix de barallar l'element tret del capell es tornara a introduir de nou i es tragueren tants com a elements hi ha en el capell i finalment s'exponguera l'orde en que els elements apareixen en el capell):

 Recórrer en k des de 0 fins a Cantitat - 1
   az = Random(entre 0 i Cantitat-1)
   
   tmp = Array(az)         
   Array(az) = Array(k)
   Array(k) = tmp
 Següent

• 2 També és possible modificar l'algoritme per a solucionar una llista la cantitat de la qual d'elements es desconeix (no té una cantitat fixa, cas típic d'una estructura que permet afegir i eliminar elements).

• 3 També és possible modificar l'algoritme, de Durnstenfeld, per a que opere en l'orde que descriu Fisher-Yates (següent a la dreta del previ). És dir, els valors obtinguts es van colocant en la posició més baixa i creixent. Note's que no hi ha pèrdua d'eficiència, i note's que el recorregut li basta aplegar fins al penúltim.

 Recórrer en k des de 0 fins a Cantitat - 2
   az = Random(entre k i Cantitat-1)
   
   tmp = Array(az)         
   Array(az) = Array(k)
   Array(k) = tmp
 Següent

• 4 Una variant interessant para determinats jocs, és aquella capaç encara de generar totes les combinacions possibles, pero que genere algunes en més freqüència que unes atres, pero encara de forma aleatòria, és dir que a pesar d'això no siga predible. Motivat per a permetre un joc que proveïxca jugades més interessants i entretingudes en un repartiment (de cartes, fiches, etc.) no tan imparcial (en quant a lo que ix, no en quant a qui ix). (per a accentuar esta característica vore la 2ª part de la secció variacions parámetrizadas). El següent pseudocódigo, obté 2 números a l'encert i abdós senyalen posicions, que són les que s'intercanvien entre sí. Si succeïx que la posició d'orige i destí és la mateixa, l'intercanvi no produïx un canvi real. També pot succeir que una o abdós posicions, hagen eixit abans ya. Abdós coses permeten que la série no siga tan diferent entre l'entrada i l'eixida, comparada en les atres implementacions. És fàcil percebre que al no usar-se com a índex el contador del bucle, sino 2 índexs elegits a l'encert, puga haver posicions que en un barallat no ixca i per tant aumenta la provabilitat de que més d'1 element mantinga a l'eixida, la mateixa posició que tenia a l'entrada. Pot aumentar-se notablement l'eficàcia de lo que tracta de fer l'algoritme si el bucle solament recorre la mitat dels elements (mitat de possibilitats de que ixca cada posició). He ací el pseudocódigo d'esta variant:

 Fi = (Tamany(Array)  2) - 1
 Recórrer en k des de 0 fins a Fi <--- Solament recorre la mitat.
    az1 = Random(entre 0 i Cantitat-1)
    az2 = Random(entre 0 i Cantitat-1)
    
    tmp = Array(az1)        <---- 'k' no es referix mai a la posició d'un element en
    el Array(az1) = Array(az2) <---  array d'esta variant, com succeïx en el restant de variants.
    Array(az2) = tmp
 Següent

• 5 Hi ha encara una forma diferent de concebre l'algoritme de barallat, que ya no s'ajusta a l'artícul, pero que encara resulta d'interés presentar ací. Siga una estructura en la que les permutació estan ya precalculadas i almagasenades i s'usa una funció random per a elegir (l'índex) com de les permutació en l'estructura és la que s'entrega. Esta variant, no obstant queda en la pràctica llimitada a séries la cantitat de les quals d'elements siguen relativament menut, donat l'espai de memòria que consumix almagasenar totes la série de permutació possibles. Encara que quan la velocitat és fonamental esta solució resulta la més apta. És ideal que una volta trobades les permutació diferents estes siguen barallades (per a que no consten l'orde creixent en que possiblement les torne la funció) i que es faça lo mateix cada cert número d'entregues.

 Variables noves:

Séries: És una estructura concorde per a contindre arrays a on cada array manté una

          permutació distinta de la série (un arbre de arrays, un atre array de arrays, etc.).
   Voltes: És un contador, per a barallar l'orde dels arrays en l'estructura series, 
          cada volta que alcança cert valor, per a favorir la aleatorietat.
   X: Un valor llímit que controla el llímit de voltes. Este valor és depenent
          de la cantitat de permutació
 Funciones accessòries
   Permutació: Seria una funció de combinatòria, que torna una estructura de arrays, 
          en totes les séries possibles, a on cada array conté una série distinta.
   Barallar: És un algoritme de barallat aleatori (com els descrits), en la particularitat 
          de que canviaria les busques dels índexs del array, en lloc del contingut.

 --- Séries És precalculada, (i de nou cada volta que canviés la cantitat d'elements).
 Series = Permutació(Cantitat) 

  Funció: BarajarAleatorio
    voltes = voltes + 1
    si voltes = x llavors  <--- 'x' és un valor que s'establix en funció 
          de la cantitat d'elements del array.
       Barallar(Séries)
       voltes = 0
    Fi si
    az = Random(entre 0 i Cantitat-1)
    Array = Séries(az)
    Tornar Array
  Fi funció

• 6 Una atra interessant variació és l'algoritme de Sattolo. Mereix ser descrit més àmpliament, en la següent secció.

Variant Sattolo

Va ser publicat en 1986 en IPL-22, per Sattolo en Information Processing Letters i té algunes particularitats que es descriuen:

• Fa el barallat, en la garantia de que cada element no ocupe la posició (a l'eixida) que ocupava inicialment (a l'entrada). Per a això es recorre a condicionar la busca aleatòria de l'element al ranc d'un element per baix de la posició actual, del que es va a reemplaçar. Esta és la particularitat interessant d'este algoritme, pero no l'única.
• Les permutació que realisa una i una atra volta, acaben sent cíclicas (es repetixen), encara que no seguixquen un orde específic, si poden presentar-se seqüències ya aparegudes.
• Hi ha permutació que jamai poden ocórrer, en séries impars (en dites séries solament alcança a la mitat de les permutació, si la série entra ordenada i s'eixecuten el número suficient de voltes). Per això no és un algoritme imparcial i deu evitar-se el seu us en jocs d'apostes (hi hauria la mitat de combinacions sense cap possibilitat real i l'atra mitat de combinacions en el doble de possibilitats), llevat que es prenguen les degudes precaucions i siga estrictament necessari que cap element repetixca la seua posició a l'eixida respecte de l'entrada, i sempre que es tinga un coneiximent expresse i exhaustiu dels resultats que pot oferir. El modo de previndre dit problema és garantisar que sempre s'usen llistes de cantitat pares, afegint quan siguen impars un últim element (que es rebuge en us).
• Este, és un atre cas d'algoritme, que per error es pot aplegar a implementar en tractar d'implementar el de Durstenfeld, ya que la diferència entra abdós implementacions és mínima.

 Recórrer en k des de Cantitat-1 fins a 1 Regresivamente
    az = Random(entre 0 i k-1) <--- EL CAMBIO: k-1, en lloc de k (és la diferència en Durstenfeld)
         
    tmp = Array(az)
    Array(az) = Array(k)
    Array(k) = tmp
 Següent

• Ya que l'algoritme per a conjunts la cantitat dels quals d'elements és impar evita la mitat de combinacions, pot interessar reproduir en algun moment atres permutació. El modo de conseguir atres combinacions (entre el restant de combinacions), consistix en solicitar, un nou barallat per a tot el conjunt menys 1 (o varis) element (per eixemple l'últim o el primer), el qual manté la seua posició. És dir, cal generar una combinació nova que mantinga a lo manco 1 element en la mateixa posició que abans. Per a això caldria generar el còdic dedicat a l'algoritme (fent-li creure que té un element menys, tal com s'expressava en una de les variants prèvies). Es conseguix aixina generar diverses séries cíclicas (pero no es garantisa que siguen tot el restant), depenent d'cual o cuales siguen els valors que s'ometen en el barallat, el cicle de la série serà més llarc o més curt. El següent pseudocódigo s'encarrega precisament d'això.

   Cantitat = Tamany(Array)
   Si es demana OmitirUno llavors
       Cantitat = Cantitat - 1
   Fi si
   Recórrer en k des de Cantitat-1 fins a 1 Regresivamente
    az = Random(entre 0 i k-1)           
    tmp = Array(az)
    Array(az) = Array(k)
    Array(k) = tmp
 Següent
       
 Que s'invocaria en la següent cridada:
 Cridada a la funció BarajarAleatorio(Array, Sattolo, OmitirUno)

Variacions parametrizadas

Hi ha algunes variacions que poden ser aplicades a totes les implementacions comentades fins al moment, be que puga variar el còdic exacte que dega afegir-se o modificar-se en cada una. Implementar estes variacions, implica afegir paràmetros en les funcions per a que en invocar-les pot elegir-se el valor necessari per a que complixca la missió encomanada.

• Una variació aplicable a totes les implementacions, consistix en fer un barallat deixant 1 element d'ells (o varis, seguits) sense barallar, és dir quedant en la mateixa posició. El modo més senzill de dur-ho a efecte és mentir a l'algoritme en qüestió fent-li creure que té un element menys, aixina baralla tots (els que l'algoritme en qüestió baralle) menys un (o eixos varis). Tal circumstància pot reclamar-se en un paràmetro opcional en la cridada a la funció. He ací el pseudocódigo que es podria afegir a qualsevol d'ells, darrere es posa l'implementació de Durstenfeld, per a apreciar lo que implica (més dalt en Sattolo, es detalla un cas, que fa us d'esta variació, per a generar séries cíclicas pero diferent a la prèvia).

 Cantitat = Tamany(Array)
 Si es demana OmitirUno llavors <--- OmitirUno seria ací un paràmetro opcional de tipo buleano
     Cantitat = Cantitat - 1
 Fi si

 Recórrer en k des de Cantitat-1 fins a 1 Regresivamente  
   az = Random(entre 0 i k)     
   tmp = Array(az)
   Array(az) = Array(k)
   Array(k) = tmp
Següent

 L'invocació a una funció que implementa esta variació en l'algoritme seria:
 Cridada a la funció BarajarAleatorio(Array, Durstenfeld, OmitirUno)

• Tal i com es comentava en la variant numerada com 4 (més arriba), a sovint hi ha jocs a on és regla del mateix (establida aixina en les regles o acordat entre els propis jugadors) que el barallat no siga excessiu (solen ser jocs d'entreteniment i no tant d'apostes pel possible risc que entranya), per a permetre un joc més interessant i entretingut (per eixemple un joc com el tute 'cabrón' accepta molt ben esta situació). Pot entendre's com a l'hora que els jugadors en pijors cartes o fiches, finalisen abans el seu joc, les seues cartes queden acumulades juntes, al temps queden en la partida els jugadors en més triumfos, que al final de la partida queden també amontonades les seues cartes, en lo que en la baralla, queden reunits els triumfos per un costat i les cartes sense valor per un atre, de modo que en barallar escassament els triumfos puguen encara estar alguna cosa acumulats i que el repartiment de cartes en una nova partida, proveïxca cartes significatives a un jugador o un atre. A voltes per a garantisar que açò mateixa no s'enterbolix, es procedix a repartir vàries cartes seguides a cada jugador, en lloc de repartir a cada jugador una carta cada volta. Abdós coses favorixen que una partida produïxca jugades més interessants (l'algoritme de dita variant es troba més dalt com a variant 4). Podem demanar a un algoritme que cada x elements del recorregut, ometa i barallats (és el pseudocódigo que es presenta a continuació). En este sentit, pot proveir-se una variació als algoritmes proporcionats per a favorir eixe escàs barallat, en esta ocasió, prenem la variant que millor conjunta en esta causa:

 Entrada:
      Un Array(0,1,2,3,4... Cantitat-1) de valors.
      Grup: un sancer que senyala cada quants s'evita un barallat.
      Bot: un sancer que indica quants seguits queden sense barallar.
 
 Cantitat = Tamany(Array)
 Fi = (Cantitat  2) - 1
 Recórrer en k des de 0 fins a Fi <--- Solament recorre la mitat.
    Si k és congruent en Grup llavors ---> congruent en, referix a l'operació mòdul 
               (que es traduïx com: si ((k mod grup) = 0) després
       k = k + bote
    En un atre cas     
       az1 = Random(entre 0 i Cantitat-1)
       az2 = Random(entre 0 i Cantitat-1)
       tmp = Array(az1)
       Array(az1) = Array(az2) <---- 'k' no es referix mai a la posició d'un element en el array d'esta variant.
       Array(az2) = tmp
    Fi si
 Següent

 L'invocació a una funció que implementa esta variació en l'algoritme seria:
 Cridada a la funció BarajarAleatorio(Array, Semibarajado, Grup=13, Bot=3)
 

Supongam una baralla de 52 cartes i supongam que volem que cada 13 cartes que baralle, es bote 3. Sent el array de 0 a 51 elements, en les posiciones k mòdul 13 (que són 0, 13, 26 i 39) en aplegar a dites posicions aumentarà k en 3 unitats, que en efecte té com a conseqüència no barallar 3 elements seguits, com són 4 voltes (4 grups de 13) hi ha 12 barallats menys. També poden especificar-se els paràmetros com els que s'ometen i els que es barallen (en l'eixemple, serien Barallen=10 i es Ometen=3) i la suma d'abdós seria l'equivalent al grup, aixina s'evita la necessitat de comprovar que bot siga menor que grup.

Deu notar-se que esta variació no evita que els valors en eixes posicions es mantinga en el seu mateix lloc (poden eixir elegides per la funció Random en qualsevol atre instant del recorregut del bucle), pero si té per efecte, que 12 elements dels 52 no siguen barallats, lo que per supost tindrà incidència, en una certa similitut entre la série a l'eixida i la série d'entrada.

• Totes les implementacions, pot ser també fàcilment modificades per a fer el barallat, solament en un subconjunt del ranc del array (no a tots), senyalant un paràmetro d'inici de l'element que s'escomença a barallar i un atre de la cantitat d'elements afectats. Açò (també) pot aplicar-se a llistes extremadament llargues a on l'ocupació de la memòria puga ser crítica, o el temps necessari per a dispondre, de tot el array barallat, no és acceptable. Dita modificació pot solucionar el problema. És imaginable un array de mil millons d'elements, a on solament es modifica 1 milló d'elements consecutius cada volta, i inclús una modificació a on es modifica 1 milló d'elements a una distància de 1000 elements entre un i un atre(l'1, el 1001, 2001, 3001, 4001.... 1001001), cada volta...

• Encara totes les implementacions, admeten encara una atra parametrización per a fer un barallat per blocs (lo que comunament en els jocs de cartes es diu tallar), que intercanvia blocs de cartes i a on els elements individuals en cada bloc manté la seua posició. En les cartes, en ser barallades a mà, cada bloc té un tamany indeterminat i independent de l'atre. Hi ha dos formes típiques de tallar: Tallar en 2 montons (de diferent tamany) en les mans, un es posa damunt del que abans estava dalt i es repetix el procés vàries voltes. Atres voltes, sobre el tapet es repartixen menuts montons (de cantitats desiguals per lo general, ya que es fa a mà) i s'arrepleguen de la taula en orde diferent al que s'ha repartit. Bàsicament est és el pseudocódigo que s'expon a continuació en la salvetat de que s'especifica un tamany de bloc que s'ajusta per a tots llevat (potser) l'últim montó. La funció rebria un paràmetro senyalant el tamany del bloc a considerar.

 Funció BarajadoAleatorio Método BarajadoEnBloques
 Cantitat = Tamany(Array)  
 Grups = Cantitat  Bloc      <--- és una divisió sancera, desprecia decimals.
 Si (Cantitat mòdul Bloc) és major que 0 llavors sumar 1 a Grups
 
 En la possibilitat de que l'últim grup no estiga complet s'intercanvia aparte.
 És dir intercanviem primer l'últim bloc pel que bloc elegit a l'encert.
 Az = Random(entre 0 i Grups-1)
 Si Az és distint de' Grups-1 llavors  <--- si el grup a l'encert és l'últim,
                                                               no fa falta intercanviar-ho.
   p = Az * Bloc
   Recórrer en k des de (Grups-1)bloc fins a Cantitat-1
     tmp = Array(p)
     Array(p) = Array(k)
     Array(k) = tmp
     p = p + 1     
   Següent   
 Fi si
 
 ----> ací va l'inserte que se senyala uns paràgrafs més avall <---
 
 Grups = Grups - 1
 Recórrer en J des de (Grups - 1) fins a 1 Regresivamente
   Az = Random(entre 0 i J)
   Si Az és distint de' J llavors <--- si el grup a l'encert és el mateix del
                                                         bucle, no fa falta intercanviar-ho.
     p = Az * Bloc
     n = Az * Bloc
     Recórrer en k des de n fins a n + Bloc - 1
       tmp = Array(p)
       Array(p) = Array(k)
       Array(k) = tmp
       p = p + 1
     Següent
   Fi si
 Següent

 I l'invocació a la funció seria aixina:
 Cridada a la funció BarajarAleatorio(Array, BarajadoEnBloques, Bloc=4)

Imagine's un mall de 28 cartes, i blocs de 4 cartes, lo que nos donaria 7 montons i seria equivalent a barallar una série de 7 elements (7 * 4 = 28), si els montons anaren de 6 cartes l'últim montó solament tindria 4 cartes, després quan ixquera este solament s'intercanviarien 4 cartes en el bloc que s'intercanvia. Es posa una série de resultats de 28 elements, en un bloc de 4, per a donar-se conte com l'afecta a un barallat d'esta manera. Obsérveses com les tuplas de 4 elements (s'ha coloreado un parell d'elles), no canvien entre sí l'orde (dels seus elements):

 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

24 25 26 27 20 21 22 23 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19

 16 17 18 19 00 01 02 03 20 21 22 23 24 25 26 27 04 05 06 07 08 09 10 11 12 13 14 15
 00 01 02 03 24 25 26 27 12 13 14 15 16 17 18 19 04 05 06 07 08 09 10 11 20 21 22 23
 04 05 06 07 16 17 18 19 20 21 22 23 24 25 26 27 12 13 14 15 00 01 02 03 08 09 10 11

Si el bloc produïx grups exactes llavors no generarà totes les permutació possibles, de fet ni encara que hi haja blocs no exactes, no generarà totes les permutació possibles. Per eixemple per a una série de 7 elements (que permet 5040 permutació distintes de la série) en un bloc de 2 genera 144 permutació, en un bloc de 3 genera només 12 permutació, en un bloc de 4, 5 i 6 solament hi ha 2 permutació possibles (ya que solament oferix 2 grups). Per això cal considerar que el número de permutació obedix més al número de grups i els elements en l'últim grup, que a la cantitat d'elements. Per últim, senyalar que si el tamany de bloc és 1, equival a barallar tots els ítems, com si no s'usara dita funcionalitat. Cal considerar que l'entrada i l'eixida varien poc entre sí, pero ya que despuix de l'eixida hi ha un nou joc, la següent entrada tindrà una permutació molt distinta de l'eixida prèvia. Si el cas és que es desija que hi haja una major possibilitat de permutació, podria barallar-se l'últim bloc (que abans estava en una atra posició i es va intercanviar en l'últim), de modo que en successives voltes quan siga canviat pel bloc en una atra posició, anirà generant una major cantitat de permutació encara que varien poc d'una a una atra en el temps. Açò pot anar especificat en un atre paràmetro o quedar fix en la variació de l'algoritme. El pseudocódigo seria el següent i es colocaria justs a on apareix esta llínea:

   ----> ací va l'inserte que se senyala uns paràgrafs més avall <---

   ' Barallar els elements interns del que ara és l'últim bloc.
   Min = ((Grups - 1) * Bloc)
   Recórrer en k des de Cantitat - 1 fins a Min Regresivamente  <---- el barallat és método Durstenfeld,
                                                          en este eixemple, pero podria ser atre
     Az = Random(entre Min i k) <---- Min: llimita el ranc inferior en lloc de
     0 tmp = Array(k)
     Array(k) = Array(Az)
     Array(Az) = tmp 
   Següent

Fixe's en les següents eixides com és barallat sempre el bloc que es va intercanviar a l'última posició i com des de llavors eixe bloc es trasllada aixina (en eixe nou orde entre els seus elements) a la següent entrada (sense canvis despuix de l'eixida). Per a estudiar el cas, ací l'eixida d'una série és l'entrada de la següent, cas que se supon que no serà cert una volta es trasllade a una aplicació real (que despuix d'un barallat hi haurà un joc tal que acaben els seus elements en un atre orde). Es marca en blau el bloc que serà l'últim en la següent etapa, i s'observa de roig eixe bloc en la següent fase, posicionat l'últim i ya barallat. Eixe bloc aixina barallat manté el seu nou orde (intern) en lo sucesivo.

 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 <---entrada
 04 05 06 07 20 21 22 23 08 09 10 11 24 25 26 27 12 13 14 15 00 01 02 03 19 16 17 18  
 19 16 17 18 04 05 06 07 24 25 26 27 08 09 10 11 20 21 22 23 00 01 02 03 14 15 13 12
 04 05 06 07 24 25 26 27 20 21 22 23 19 16 17 18 14 15 13 12 08 09 10 11 02 01 00 03
 02 01 00 03 14 15 13 12 08 09 10 11 20 21 22 23 19 17 16 18 07 04 07 05 26 25 24 27
 14 15 12 13 02 08 09 10 11 01 00 03 19 17 16 18 07 04 07 05 20 21 22 23 25 27 24 26 <--- l'últim 

bloc s'intercanvia en si mateixa esta volta.

Com es pot apreciar, esta variació també permet generar permutació aptes para quan es desija generar jugades interessants i entretingudes en jocs que ho necessiten, i en canvi no és acceptable en jocs en apostes.

Vore també

• Aleatoriedad
• Entropía (informació)
• Número aleatori
• Proves de aleatorietat
• Seqüència pseudoaleatoria
• Teoria de provabilitat
• Variable aleatòria