Какова логика этой реализации _.shuffle?

Question

Может ли кто-нибудь изменить меня, как это работает?

Я немного смущен относительно того, как мы гарантируем, что генерируемое случайное число (так называемый индекс, который мы пытаемся получить) var rand является уникальным, чтобы гарантировать, что мы перетасовываем данный массив.

Например. учитывая [1,2,3,4], мы возвращаем [3,4,2,1], а не [3,3,4,4], потому что генерируемое случайное число повторяет индекс 2 и 3?

_.shuffle = function(array) { 
 
    var newArr = array.slice(); 
 
     for (var i=array.length-1; i>0; i--) { 
 
     var rand = Math.round(Math.random() * i); 
 
     var temp = newArr[rand]; 
 
     newArr[rand] = newArr[i]; 
 
     newArr[i] = temp; 
 
     } 
 
    return newArr; 
 
    };

Answer 1

ran не обязательно должен быть уникальным.

Для каждой итерации цикла for алгоритм перетасовки будет заменять два элемента в массиве.

Как таковой, это нормально, если ran не является уникальным, так как мы можем повторно обменять два элемента в несколько раз, не вызывая проблем.

Также обратите внимание, что массив мутирован. Поэтому для каждой итерации цикла мы используем последнее состояние массива. Это означает, что мы не создаем дубликаты, если мы меняем один и тот же индекс несколько раз.

Answer 2

Это называется Fisher-Yates перетасовать. Википедия имеет довольно сложную статью об этом: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Answer 3

annotated version of the source прочитать:

Перемешать коллекцию, используя современную версию Fisher-Yates shuffle.

И нет, rand не генерируется уникальный, это может быть одинаковое число в разных итерациях. Но по дизайну алгоритма он всегда указывает на неперемешанный элемент (в диапазоне [0, i]).

Answer 4

Это хороший пример плохой реализации обработки случайных значений.

С Math.round вы получаете результаты, которые на самом деле не равны между собой, то есть в начале и конце всего диапазона вы получаете только половину значений, которые вам нужно иметь.

var rand = Math.round(Math.random() * i); 
//    ^^^^^ 

var _ = {}, 
 
    i, 
 
    array = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], 
 
    count = { }; 
 

 
_.shuffle = function (array) { 
 
    var newArr = array.slice(); 
 
    for (var i = array.length - 1; i > 0; i--) { 
 
     var rand = Math.round(Math.random() * i); 
 
     var temp = newArr[rand]; 
 
     newArr[rand] = newArr[i]; 
 
     newArr[i] = temp; 
 
    } 
 
    return newArr; 
 
}; 
 

 
array.forEach(function (a) { 
 
    count[a] = count[a] || []; 
 
}); 
 
for (i = 0; i < 100000; i++) { 
 
    _.shuffle(array).forEach(function (a, i) { 
 
     count[a][i] = (count[a][i] || 0) + 1; 
 
    }); 
 
} 
 
console.log(count);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Пример с распределением с

var rand = Math.floor(Math.random() * (i + 1)); 
//    ^^^^^     ^^^ 

var _ = {}, 
 
    i, 
 
    array = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], 
 
    count = { }; 
 

 
_.shuffle = function (array) { 
 
    var newArr = array.slice(); 
 
    for (var i = array.length - 1; i > 0; i--) { 
 
     var rand = Math.floor(Math.random() * (i + 1)); 
 
     var temp = newArr[rand]; 
 
     newArr[rand] = newArr[i]; 
 
     newArr[i] = temp; 
 
    } 
 
    return newArr; 
 
}; 
 

 
array.forEach(function (a) { 
 
    count[a] = count[a] || []; 
 
}); 
 
for (i = 0; i < 100000; i++) { 
 
    _.shuffle(array).forEach(function (a, i) { 
 
     count[a][i] = (count[a][i] || 0) + 1; 
 
    }); 
 
} 
 
console.log(count);

.as-console-wrapper { max-height: 100% !important; top: 0; }