Let be a list containing the 26 letters of the alphabet from A to Z. We mix the list with the Fisher-Yates algorithm (see https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). We are interested in the first letter of the table :
- In theory, each letter has the same probability of being in the first position: 1/26 ~ 3.85%.
- In practice, this is not the case! As the distribution below shows, the probability of finding B is 5.14% against 2.89% for Z. B has 1.78x more chances than Z to be in first position (almost 2x more which is huge).
Here is the code I used:
"use strict";
// mix
const mix = array => {
const { length: n } = array;
for (let i = 0; i < n; i++) {
const x = Math.floor(Math.random() * n);
[array[i], array[x]] = [array[x], array[i]];
}
return array;
};
const A = 'A'.charCodeAt(0);
const NB_LETTERS = 26;
const TABLE = {};
for (let i = 0; i < NB_LETTERS; i++) TABLE[String.fromCharCode(A + i)] = 0;
for (let N = 1; ; N++) {
// init
const array = [];
for (let i = 0; i < NB_LETTERS; i++) array[i] = String.fromCharCode(A + i);
mix(array);
TABLE[array[0]]++;
if (N % 1000000 === 0) {
console.log('');
console.log("N =", N);
console.log(
Object.entries(TABLE)
.map(([letter, n]) => {
const freq = n / N;
return letter + '\t' + freq.toString().replace('.', ',');
})
.join('\n')
);
}
}
Questions:
- Do you get the same results?
- Is it from
Math.random()
? I think so ... do you know of an alternative that would give a uniform distribution?
Thanks in advance !
Aucun commentaire:
Enregistrer un commentaire