vendredi 2 août 2019

Can Fisher-Yates shuffle produce all playing card permutations?

I'm using the standard Fisher-Yates algorithm to randomly shuffle a deck of cards in an array. However, I'm unsure if this will actually produce a true distribution of all possible permutations of a real-world shuffled deck of cards.

V8's Math.random only has 128-bits of internal state. Since there are 52 cards in a deck, 52 factorial would require 226-bits of internal state to generate all possible permutations.

However, I'm unsure if this applies when using Fisher-Yates since you aren't actually generating each possible but just getting one position randomly out of 52.

function shuffle(array) {
  var m = array.length, t, i;

  while (m) {
    i = Math.floor(Math.random() * m--);
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}




Aucun commentaire:

Enregistrer un commentaire