【Underscore.js】_.shuffleを読んだ

jashkenas/underscoreの_.shuffleを読んだ。

概要

Returns a shuffled copy of the list, using a version of the Fisher-Yates shuffle.

Fisher–Yates shuffleを用いて、シャッフルされたリストのコピーを返す。

x = _.shuffle([1,2,3]);
console.log(x); // [2, 3, 1]

ソースコード

_.shuffle = function(obj) {
    var set = isArrayLike(obj) ? obj : _.values(obj);
    var length = set.length;
    var shuffled = Array(length);
    for (var index = 0, rand; index < length; index++) {
      rand = _.random(0, index);
      if (rand !== index) shuffled[index] = shuffled[rand];
      shuffled[rand] = set[index];
    }
    return shuffled;
  };

このアルゴリズムでは、与えられたリスト(obj)の最初の数字から末尾の数字までが1つずつ選ばれていく。

そして、結果として返すリスト(shuffled)のrand番目に、選んだ値を代入していく。

もし、すでにshuffledのrand番目に数値が入っていたら、index番目とスワップする。

参考

jashkenas/underscore

世界最速の配列シャッフルアルゴリズム、Fisher-Yatesアルゴリズム: PandaNoir