Перемешивающий алгоритм Ярмарка? (Javascript)

Question

Я столкнулся с приведенным ниже алгоритмом для перетасовки массива в Javascript. Похоже, что он отличается от Shuffle от Fisher-Yates тем, что диапазон доступных «свопов» увеличивается с помощью счетчика for-loop. Это похоже на то, как ведет себя версия Фишера-Йейтс. Мне любопытно, действительно ли это правильный алгоритм. Неужели это Фишер-Йейтс? Это предвзято?

Если кто-то может предоставить некоторый код для проверки частоты перестановок, которые он генерирует, это будет бонус.

<script> 
var shuffle = function (myArray) { 
    var random = 0; 
    var temp = 0; 
    console.log(myArray); 
    for (i = 1; i < myArray.length; i++) { 
     random = Math.round(Math.random() * i); 
     console.log(random + '\n'); 
     temp = myArray[i]; 
     myArray[i] = myArray[random]; 
     myArray[random] = temp; 
     console.log(myArray); 
    } 
    return myArray; 
} 

var arr = [1, 2, 3, 4]; 

shuffle(arr); 

</script> 

Answer 1

Нет, это некрасивая тасовка.

Math.random() * i является равномерной случайной величиной с плавающей точкой между 0 и i, но Math.round(Math.random() * i) не выбирает целые числа между 0 и i одинаково. Например, когда i равно 2, значения в диапазоне [0, 0.5) округляются до 0, значения в диапазоне [0,5, 1,5) округляются до 1, а значения в диапазоне (1,5, 2) округляются до 2. Это означает вместо того, чтобы выбирать 0, 1 и 2 одинаково часто, 1 выбирается с вероятностью 0,5, а 0 и 2 выбираются с вероятностью 0,25 каждый.

Math.floor(Math.random * (i + 1)) будет правильным.

Вы можете проверить это статистически: перетасовать массив [0, 1, 2] 10000 раз и посмотреть, как часто 2 остается в конце массива. Это должно быть около 3333, но из-за предвзятости это будет больше похоже на 2500.

Кроме этого алгоритм является правильным и может быть описан как Fisher-Yates в обратном порядке. Вы можете доказать это правильно по индукции. Базовый случай n = 1 тривиален. Шаг индукции также относительно прост: если вы получили равномерную случайную перестановку n элементов, а затем вставляете n + 1-й элемент при равномерно случайном индексе от 0 до n + 1, то у вас есть случайный перестановка n + 1 элементов.