javascript - JavaScript配列をランダム化(シャッフル)する方法は?

Question

私はこのような配列を持っています:

var arr1 = ["a", "b", "c", "d"];

ランダム化/シャッフルするにはどうすればよいですか?

score 2048 · Accepted Answer

事実上の偏りのないシャッフルアルゴリズムは、Fisher-Yates (別名 Knuth) Shuffleです。

ここで素晴らしいビジュアライゼーションを見ることができます (およびこれにリンクされている元の投稿)

function shuffle(array) {
  let currentIndex = array.length,  randomIndex;

  // While there remain elements to shuffle...
  while (currentIndex != 0) {

    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex--;

    // And swap it with the current element.
    [array[currentIndex], array[randomIndex]] = [
      array[randomIndex], array[currentIndex]];
  }

  return array;
}

// Used like so
var arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);

使用されているアルゴリズムに関する詳細情報。

score 992 · Accepted Answer

以下は、Fisher-Yates の最適化されたバージョンであるDurstenfeld shuffleの JavaScript 実装です。

/* Randomize array in-place using Durstenfeld shuffle algorithm */
function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

元の配列要素ごとにランダムな要素を選択し、カードのデッキからランダムに選択するように、次の抽選から除外します。

この巧妙な除外は、選択された要素を現在の要素と交換し、残りから次のランダムな要素を選択し、最適な効率のために逆方向にループして、ランダムな選択が単純化されるようにし (常に 0 から開始できます)、最終要素をスキップします。

アルゴリズムのランタイムはO(n). シャッフルはその場で行われることに注意してください。元の配列を変更したくない場合は、最初にでコピーを作成して.slice(0)ください。

編集: ES6 / ECMAScript 2015 への更新

新しい ES6 では、一度に 2 つの変数を割り当てることができます。これは、1 行のコードで実行できるため、2 つの変数の値を交換したい場合に特に便利です。この機能を使用して、同じ関数の短い形式を次に示します。

function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

score 186 · Accepted Answer

警告！
このアルゴリズムの使用は非効率的で偏りが強いため、お勧めできません。コメントを参照してください。アイデアはそれほど珍しいものではないため、将来の参照用にここに残しています。

[1,2,3,4,5,6].sort( () => .5 - Math.random() );

このhttps://javascript.info/array-methods#shuffle-an-arrayチュートリアルでは、違いを簡単に説明しています。

score 73 · Accepted Answer

Array のプロトタイプとして使用できます (または使用する必要があります)。

クリストフD より:

Array.prototype.shuffle = function() {
  var i = this.length, j, temp;
  if ( i == 0 ) return this;
  while ( --i ) {
     j = Math.floor( Math.random() * ( i + 1 ) );
     temp = this[i];
     this[i] = this[j];
     this[j] = temp;
  }
  return this;
}

score 72 · Accepted Answer

underscore.js ライブラリを使用します。この場合、この方法_.shuffle()は便利です。メソッドの例を次に示します。

var _ = require("underscore");

var arr = [1,2,3,4,5,6];
// Testing _.shuffle
var testShuffle = function () {
  var indexOne = 0;
    var stObj = {
      '0': 0,
      '1': 1,
      '2': 2,
      '3': 3,
      '4': 4,
      '5': 5
    };
    for (var i = 0; i < 1000; i++) {
      arr = _.shuffle(arr);
      indexOne = _.indexOf(arr, 1);
      stObj[indexOne] ++;
    }
    console.log(stObj);
};
testShuffle();

score 59 · Accepted Answer

新着！

より短く、おそらく * より高速な Fisher-Yates シャッフルアルゴリズム

それはwhileを使用します---
ビットごとにフロア (10 進数 10 桁 (32 ビット) までの数値)
不必要な閉鎖やその他のものを削除しました

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*(--c+1)|0,d=a[c],a[c]=a[b],a[b]=d
}

スクリプトサイズ(関数名にfyを使用): 90バイト

デモ http://jsfiddle.net/vvpoma8w/

*おそらくクロムを除くすべてのブラウザでより高速です。

ご不明な点がございましたら、お気軽にお問い合わせください。

編集

はい、それはより高速です

パフォーマンス: http://jsperf.com/fyshuffle

上位投票された関数を使用します。

編集余分な計算があり（--c + 1は必要ありません）、誰も気づきませんでした

より短い (4 バイト) & より高速 (テストしてください!)。

function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
 c=a.length;while(c)b=Math.random()*c--|0,d=a[c],a[c]=a[b],a[b]=d
}

別の場所にキャッシュしてvar rnd=Math.randomから使用rnd()すると、大きな配列でのパフォーマンスもわずかに向上します。

http://jsfiddle.net/vvpoma8w/2/

読み取り可能なバージョン(元のバージョンを使用してください。これは遅く、変数はクロージャ & ";" のように役に立ちません。コード自体も短いです ... 多分このHow to 'minify' Javascript code を読んでください。上記のような JavaScript ミニファイアで次のコードを圧縮します。)

function fisherYates( array ){
 var count = array.length,
     randomnumber,
     temp;
 while( count ){
  randomnumber = Math.random() * count-- | 0;
  temp = array[count];
  array[count] = array[randomnumber];
  array[randomnumber] = temp
 }
}

score 24 · Accepted Answer

@Laurens Holstsの回答に追加します。これは 50% 圧縮されています。

function shuffleArray(d) {
  for (var c = d.length - 1; c > 0; c--) {
    var b = Math.floor(Math.random() * (c + 1));
    var a = d[c];
    d[c] = d[b];
    d[b] = a;
  }
  return d
};

score 21 · Accepted Answer

この変種は、この質問の複製に関する「作成者によって削除された」回答にぶら下がっていることがわかりました。すでに多くの賛成票がある他の回答とは異なり、これは次のとおりです。

実はランダム
インプレースではない (したがって、shuffledではなく名前shuffle)
複数のバリアントがあり、ここにはまだ存在しません

これが使用中のjsfiddleです。

Array.prototype.shuffled = function() {
  return this.map(function(n){ return [Math.random(), n] })
             .sort().map(function(n){ return n[1] });
}

score 21 · Accepted Answer

ES2015では、これを使用できます：

Array.prototype.shuffle = function() {
  let m = this.length, i;
  while (m) {
    i = (Math.random() * m--) >>> 0;
    [this[m], this[i]] = [this[i], this[m]]
  }
  return this;
}

使用法：

[1, 2, 3, 4, 5, 6, 7].shuffle();

score 19 · Accepted Answer

//one line solution
shuffle = (array) => array.sort(() => Math.random() - 0.5);


//Demo
let arr = [1, 2, 3];
shuffle(arr);
alert(arr);

https://javascript.info/task/shuffle

Math.random() - 0.5は正または負の乱数であるため、ソート関数は要素をランダムに並べ替えます。

score 16 · Accepted Answer

var shuffle = function(array) {
   temp = [];
   originalLength = array.length;
   for (var i = 0; i < originalLength; i++) {
     temp.push(array.splice(Math.floor(Math.random()*array.length),1));
   }
   return temp;
};

score 10 · Accepted Answer

フィッシャー・イェーツのJavaScriptでのシャッフル. 2 つのユーティリティ関数 (swap と randInt) を使用すると、他の回答と比較してアルゴリズムが明確になるため、ここに投稿します。

function swap(arr, i, j) { 
  // swaps two elements of an array in place
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
function randInt(max) { 
  // returns random integer between 0 and max-1 inclusive.
  return Math.floor(Math.random()*max);
}
function shuffle(arr) {
  // For each slot in the array (starting at the end), 
  // pick an element randomly from the unplaced elements and
  // place it in the slot, exchanging places with the 
  // element in the slot. 
  for(var slot = arr.length - 1; slot > 0; slot--){
    var element = randInt(slot+1);
    swap(arr, element, slot);
  }
}

score 10 · Accepted Answer

再帰的な解決策:

function shuffle(a,b){
    return a.length==0?b:function(c){
        return shuffle(a,(b||[]).concat(c));
    }(a.splice(Math.floor(Math.random()*a.length),1));
};

score 10 · Accepted Answer

ベンチマーク

最初に結果を見てから、以下の各実装を見てみましょうshuffle-

スプライスが遅い

spliceまたはをループで使用するソリューションshiftは、非常に遅くなります。これは、配列のサイズを大きくすると特に顕著です。素朴なアルゴリズムでは -

入力配列内のrand位置を取得します。it
t[i]出力に追加
splicei配列からの位置t

遅い効果を誇張するために、100 万個の要素の配列でこれを示します。次のスクリプトは約 30 秒-

const shuffle = t =>
  Array.from(sample(t, t.length))

function* sample(t, n)
{ let r = Array.from(t)
  while (n > 0 && r.length)
  { const i = rand(r.length) // 1
    yield r[i]               // 2
    r.splice(i, 1)           // 3
    n = n - 1
  }
}

const rand = n =>
  Math.floor(Math.random() * n)

function swap (t, i, j)
{ let q = t[i]
  t[i] = t[j]
  t[j] = q
  return t
}

const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via splice")
const result = shuffle(bigarray)
console.timeEnd("shuffle via splice")
document.body.textContent = JSON.stringify(result, null, 2)

body::before {
  content: "1 million elements via splice";
  font-weight: bold;
  display: block;
}

ポップは速い

秘訣はsplice、代わりに超効率的なを使用することではありませんpop。これを行うには、典型的なsplice呼び出しの代わりに、あなたは -

接合する位置を選択し、i
最後の要素と交換t[i]し、t[t.length - 1]
t.pop()結果に追加

今では、100 ミリ秒未満で 100shuffle万個の要素を処理できます。

const shuffle = t =>
  Array.from(sample(t, t.length))

function* sample(t, n)
{ let r = Array.from(t)
  while (n > 0 && r.length)
  { const i = rand(r.length) // 1
    swap(r, i, r.length - 1) // 2
    yield r.pop()            // 3
    n = n - 1
  }
}

const rand = n =>
  Math.floor(Math.random() * n)

function swap (t, i, j)
{ let q = t[i]
  t[i] = t[j]
  t[j] = q
  return t
}

const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via pop")
const result = shuffle(bigarray)
console.timeEnd("shuffle via pop")
document.body.textContent = JSON.stringify(result, null, 2)

body::before {
  content: "1 million elements via pop";
  font-weight: bold;
  display: block;
}

さらに速く

上記の 2 つの実装は、新しい出力配列shuffleを生成します。入力配列は変更されません。これは私の好みの作業方法ですが、その場でシャッフルすることでさらに速度を上げることができます。

10ミリ秒未満でshuffle100 万要素未満-

function shuffle (t)
{ let last = t.length
  let n
  while (last > 0)
  { n = rand(last)
    swap(t, n, --last)
  }
}

const rand = n =>
  Math.floor(Math.random() * n)

function swap (t, i, j)
{ let q = t[i]
  t[i] = t[j]
  t[j] = q
  return t
}

const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle in place")
shuffle(bigarray)
console.timeEnd("shuffle in place")
document.body.textContent = JSON.stringify(bigarray, null, 2)

body::before {
  content: "1 million elements in place";
  font-weight: bold;
  display: block;
}

score 9 · Accepted Answer

ES6 機能を使用した最新の短いインラインソリューション:

['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);

(教育目的のため)

score 8 · Accepted Answer

Fisher-Yates shuffle アルゴリズムと ES6を使用:

// Original array
let array = ['a', 'b', 'c', 'd'];

// Create a copy of the original array to be randomized
let shuffle = [...array];

// Defining function returning random value from i to N
const getRandomValue = (i, N) => Math.floor(Math.random() * (N - i) + i);

// Shuffle a pair of two elements at random position j
shuffle.forEach( (elem, i, arr, j = getRandomValue(i, arr.length)) => [arr[i], arr[j]] = [arr[j], arr[i]] );

console.log(shuffle);
// ['d', 'a', 'b', 'c']

score 6 · Accepted Answer

厳密モードを使用したフィッシャー・イェーツのさらに別の実装:

function shuffleArray(a) {
    "use strict";
    var i, t, j;
    for (i = a.length - 1; i > 0; i -= 1) {
        t = a[i];
        j = Math.floor(Math.random() * (i + 1));
        a[i] = a[j];
        a[j] = t;
    }
    return a;
}

score 5 · Accepted Answer

配列をランダム化する

 var arr = ['apple','cat','Adam','123','Zorro','petunia']; 
 var n = arr.length; var tempArr = [];

 for ( var i = 0; i < n-1; i++ ) {

    // The following line removes one random element from arr 
     // and pushes it onto tempArr 
     tempArr.push(arr.splice(Math.floor(Math.random()*arr.length),1)[0]);
 }

 // Push the remaining item onto tempArr 
 tempArr.push(arr[0]); 
 arr=tempArr;

score 4 · Accepted Answer

最短arrayShuffle関数

function arrayShuffle(o) {
    for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
}

score 3 · Accepted Answer

Array.prototype.shuffle=function(){
   var len = this.length,temp,i
   while(len){
    i=Math.random()*len-- |0;
    temp=this[len],this[len]=this[i],this[i]=temp;
   }
   return this;
}

score 3 · Accepted Answer

パイに指を入れるだけです。ここでは、Fisher Yates shuffle の再帰的な実装を紹介します (と思います)。一様なランダム性を与えます。

注: ~~(二重チルダ演算子) は、実際にはMath.floor()正の実数のように動作します。ただのショートカットです。

var shuffle = a => a.length ? a.splice(~~(Math.random()*a.length),1).concat(shuffle(a))
                            : a;

console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));

編集:上記のコードはを使用しているため O(n^2) です.splice()が、スワップトリックによって O(n) のスプライスとシャッフルを排除できます。

var shuffle = (a, l = a.length, r = ~~(Math.random()*l)) => l ? ([a[r],a[l-1]] = [a[l-1],a[r]], shuffle(a, l-1))
                                                              : a;

var arr = Array.from({length:3000}, (_,i) => i);
console.time("shuffle");
shuffle(arr);
console.timeEnd("shuffle");

問題は、JS が大きな再帰に協力できないことです。この特定のケースでは、配列のサイズは、ブラウザエンジンと不明な事実に応じて 3000 ～ 7000 程度に制限されます。

score 2 · Accepted Answer

他の解決策に従って、ロコまたは新しい不変配列に適用することを検討すると、推奨される実装は次のとおりです。

Array.prototype.shuffle = function(local){
  var a = this;
  var newArray = typeof local === "boolean" && local ? this : [];
  for (var i = 0, newIdx, curr, next; i < a.length; i++){
    newIdx = Math.floor(Math.random()*i);
    curr = a[i];
    next = a[newIdx];
    newArray[i] = next;
    newArray[newIdx] = curr;
  }
  return newArray;
};

score 1 · Accepted Answer

Fisher-Yates のこのバリエーションは、要素をそれ自体と交換することを回避するため、わずかに効率的です。

function shuffle(array) {
  var elementsRemaining = array.length, temp, randomIndex;
  while (elementsRemaining > 1) {
    randomIndex = Math.floor(Math.random() * elementsRemaining--);
    if (randomIndex != elementsRemaining) {
      temp = array[elementsRemaining];
      array[elementsRemaining] = array[randomIndex];
      array[randomIndex] = temp;
    }
  }
  return array;
}

score -1 · Accepted Answer

//doesn change array
Array.prototype.shuffle = function () {
    let res = [];
    let copy = [...this];

    while (copy.length > 0) {
        let index = Math.floor(Math.random() * copy.length);
        res.push(copy[index]);
        copy.splice(index, 1);
    }

    return res;
};

let a=[1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(a.shuffle());

score -2 · Accepted Answer

$=(m)=>console.log(m);

//----add this method to Array class 
Array.prototype.shuffle=function(){
  return this.sort(()=>.5 - Math.random());
};

$([1,65,87,45,101,33,9].shuffle());
$([1,65,87,45,101,33,9].shuffle());
$([1,65,87,45,101,33,9].shuffle());
$([1,65,87,45,101,33,9].shuffle());
$([1,65,87,45,101,33,9].shuffle());

javascript - JavaScript配列をランダム化(シャッフル)する方法は?

64 に答える 64

編集: ES6 / ECMAScript 2015 への更新

Related

Reference