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 :
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:
Math.random()
? I think so ... do you know of an alternative that would give a uniform distribution?Thanks in advance !
The shuffle algorithm in the function mix
is not correctly implemented.
The algorithm in the referenced Wikipedia article stipulates that the range to take a random number from should be different in each iteration, which is not the case in your implementation, hence the non-homogeneous distribution.
Make this correction:
const x = i + Math.floor(Math.random() * (n - i));
Other implementations (with some optimisations) can be found at How to randomize (shuffle) a JavaScript array?