Baralla de cartes

Remenant cartes o com desordenar un array

L'altre dia per distreure'm vaig estar implementant un joc de cartes al que jugàvem de petits, val a dir que no és un àrea que domini, de fet és el primer que faig, però bé, una de les coses a fer és remenar la baralla, i aquí vaig cometre un error que m'havia passat desapercebut fins avui.

Així és com les estava creant i remenant fins ara:

const baralla = ['ors', 'copes', 'espases', 'bastos']
  .map(pal => [...Array(12).keys()].map(num => ({ pal, num: num + 1 })))
  .flat();

for (let i = baralla.length; i--; ) {
  const j = Math.floor(Math.random() * baralla.length);
  [baralla[i], baralla[j]] = [baralla[j], baralla[i]];
}

Aparentment sembla correcte, per cada posició a la baralla la permuto amb qualsevol altre, fins que he passat per totes les posicions. De fet fa la feina i la baralla queda efectivament remenada, la qüestió és, queda ben remenada tal que la probabilitat de que qualsevol carta caigui en qualsevol posició sigui la mateixa? Doncs resulta que no...

Aquesta és una implementació errònia de l'algoritme de Knuth. A mi el càlcul de probabilitats i permutacions sempre m'ha costat bastant, però segur que recordareu de l'escola que el nombre de permutacions possibles sense repetició d'una llista d'n elements és n! (https://www.sangakoo.com/ca/temes/permutacions-sense-repeticio).

Si ens fixem en l'algoritme anterior donat que a cada iteració j pot ser un valor entre 0 i n i que hi ha n iteracions, tenim que pot generar n^n combinacions, i com que n^n > n! per n>2, hi haurà combinacions repetides, ara bé, es repetiran els mateixos cops i per tant no afecta la distribució? Aquí la demostració matemàtica ja se m'escapa però és fàcil de veure que per n=3 tenim 3! = 6 combinacions possibles, mentre que l'algoritme anterior generaria 3³ = 27 possibles combinacions que no és divisible per 6 i per tant no totes tenen la mateixa probabilitat.

Vist l'error i perquè els jugadors no se m'enfadin procedim a implementar correctament l'algoritme de Knuth:

for (let i = baralla.length - 1; i > 0; i--) {
  const j = ~~(Math.random() * (i + 1));
  [baralla[i], baralla[j]] = [baralla[j], baralla[i]];
}