どのようにランダム(シャッフル)JavaScriptの配列?
-
20-09-2019 - |
質問
い配列のようになります:
var arr1 = ["a", "b", "c", "d"];
たいのですがランダマイズ/シャッフルです。
解決
の事実上の偏りのないシャッフルアルゴリズムのフィッシャー-イェーツ(通称Knuth)選択することができます
見 https://github.com/coolaj86/knuth-shuffle
function shuffle(array) {
var currentIndex = array.length, temporaryValue, randomIndex;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// And swap it with the current element.
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
// Used like so
var arr = [2, 11, 37, 42];
arr = shuffle(arr);
console.log(arr);
一部の詳細情報 のアルゴリズム 使用します。
他のヒント
ここで DurstenfeldのJavaScript実装はに、コンピュータに最適化をシャッフルされますフィッシャーイエーツのバージョン:
/**
* Randomize array element order 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;
}
}
フィッシャーイエーツアルゴリズムは、各元の配列要素のための1つのランダム要素をピッキングし、次のドローからそれを排除することにより作用します。ただ、ランダムにカードのデッキから取り出すような。
この除外は、現在の要素で採取要素を交換し、次に残りの部分から次のランダム要素を選ぶことにより(コンピュータで使用するためDurstenfeldによって発明)巧妙な方法で行われます。最適な効率のために、ループがランダムピックが簡略化されていること(それは常に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]];
}
}
[コミュニティ編集:この答えは間違っています。コメントを参照してください。アイデアはその稀ではありませんので、それは今後の参考のためにここに残されている。
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
一つは、可能性(または必要があります)アレイからのプロトタイプとしてそれを使用します。ポップ>クリストファーよります:
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;
}
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();
行うことができるので簡単に地図や並び替え:
let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]
let shuffled = unshuffled
.map((a) => ({sort: Math.random(), value: a}))
.sort((a, b) => a.sort - b.sort)
.map((a) => a.value)
- また配列内の各要素に、オブジェクトでは、ランダムソートキー
- いうランダムキーの使用
- まunmapに、元のオブジェクト
できるシャッフルで多型配列のソートはランダムとしてMath.ランダムである程度の良さです。
らの要素は、ソートに対し一貫したキーは再生して繰り返し、比較を引きから、同じ分布、乱数の発生源の流通Math.ランダムが解除されます。
NEW!
短&そらく*高速フィッシャー-イェイツシャッフルアルゴリズム
- 使用すが---
- ビット単位の階(数字10桁の半角数字(32bit))
- 削除されunecessaryクロージャー-その他のもの
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として機能名90bytes
デモ http://jsfiddle.net/vvpoma8w/
*早くすべてのブラウザ以外のchrome.
ご質問のある方でお願いします。
編集
あり高速
性能: http://jsperf.com/fyshuffle
使用上の票を投じます。
編集 がありました計算の余ったな--c+1) および好気
短い4bytes)&速試験です!)
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()
も若干上昇学三田キャンパスにて行われる大きなarrays.
http://jsfiddle.net/vvpoma8w/2/
可読版 (使用のバージョン。この遅varsは無駄なように、クロージャー-";"は、コードそのものが短...も読み取るこ どのように'minify'Javascriptコード ,ねることができずに圧縮もしくは、下記コードをjavascript minifiersのように記す。)
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
}
}
小さなアレイのための非常に簡単な方法は、単にこれです:
const someArray = [1, 2, 3, 4, 5];
someArray.sort(() => Math.random() - 0.5);
これはおそらく、非常に効率的ではないのですが、小さな配列のために、これはうまく動作します。ここでは、それがどのようにランダムに(またはしない)見ることができるように、それはあなたのユースケースに合うかどうかの例です。
const resultsEl = document.querySelector('#results');
const buttonEl = document.querySelector('#trigger');
const generateArrayAndRandomize = () => {
const someArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
someArray.sort(() => Math.random() - 0.5);
return someArray;
};
const renderResultsToDom = (results, el) => {
el.innerHTML = results.join(' ');
};
buttonEl.addEventListener('click', () => renderResultsToDom(generateArrayAndRandomize(), resultsEl));
<h1>Randomize!</h1>
<button id="trigger">Generate</button>
<p id="results">0 1 2 3 4 5 6 7 8 9</p>
一部の回答が短縮されることをES6構文です。
ES6、繰り返し
const getShuffledArr = arr => {
const newArr = arr.slice()
for (let i = newArr.length - 1; i > 0; i--) {
const rand = Math.floor(Math.random() * (i + 1));
[newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
}
return newArr
};
個人的にこの機能を利用し、比較的簡単である私の試験Google Chrome最も効率的な比その他純粋版).
シャッフルな配列の場所
function shuffledArr (array){
for (let i = array.length - 1; i > 0; i--) {
const rand = Math.floor(Math.random() * (i + 1));
[array[i], array[rand]] = [array[rand], array[i]]
}
}
信頼性と性能
ご覧のとおりこのページにおいて誤解を提供する。そこで、信頼性、性能、書いた以下の機能を試験合純副作用はありません)配列のランダマイズ処理を施す。までのすべてのオプションこれらの答えです。
function testShuffledArrayFun(getShuffledArrayFun){
const arr = [0,1,2,3,4,5,6,7,8,9]
let countArr = arr.map(el=>{
return arr.map(
el=> 0
)
}) // For each possible position in the shuffledArr and for
// each possible value, we'll create a counter.
const t0 = performance.now()
const n = 1000000
for (let i=0 ; i<n ; i++){
// We'll call getShuffledArrayFun n times.
// And for each iteration, we'll increment the counter.
const shuffledArr = getShuffledArrayFun(arr)
shuffledArr.forEach(
(value,key)=>{countArr[key][value]++}
)
}
const t1 = performance.now()
console.log(`Count Values in position`)
console.table(countArr)
const frequencyArr = countArr.map( positionArr => (
positionArr.map(
count => count/n
)
))
console.log("Frequency of value in position")
console.table(frequencyArr)
console.log(`total time: ${t1-t0}`)
}
その他のオプション
ES6、再帰的
const getShuffledArr = arr => {
if (arr.length === 1) {return arr};
const rand = Math.floor(Math.random() * arr.length);
return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))];
};
ES6純用の配列になります。地図
function getShuffledArr (arr){
return [...arr].map( (_, i, arrCopy) => {
var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) );
[arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]]
return arrCopy[i]
})
}
ES6純用の配列になります。削減
function getShuffledArr (arr){
return arr.reduce(
(newArr, _, i) => {
var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) );
[newArr[rand], newArr[i]] = [newArr[i], newArr[rand]]
return newArr
}, [...arr]
)
}
稿型のための純粋な配列の機能ランダマイズ処理を施
どちらかをお使いいただけます。
type GetShuffledArr= <T>(arr:Array<T>) => Array<T>
interface IGetShuffledArr{
<T>(arr:Array<T>): Array<T>
}
@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
};
//one line solution
shuffle = (array) => array.sort(() => Math.random() - 0.5);
//Demo
let arr = [1, 2, 3];
shuffle(arr);
alert(arr);
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();
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;
};
この変異体作品を"投稿者によって削除されて"答えの複製はこの質問です。とは異なり、その他の回答が多くupvotesです:
- 実際にランダム
- ない場所までの
shuffled
名によshuffle
) - 存在しないこと複数の異
Array.prototype.shuffled = function() {
return this.map(function(n){ return [Math.random(), n] })
.sort().map(function(n){ return n[1] });
}
あなたは簡単にそれを行うことができます:
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
で参照してください。
再帰的な解決策ます:
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));
};
フィッシャーイエーツをシャッフル。 2つのユーティリティ関数(スワップと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);
}
}
まず第一に、の偉大な視覚的な比較のために、ここでのrel="nofollow"> href="http://bost.ocks.org/mike/shuffle/compare.html"ルック
あなたは上記のリンクを簡単に見ている場合は、 第二に、あなたは 編集:@gregersで指摘したように、比較関数は、あなたがrandom order
のソートは以下に示すように、非常に簡単かつ高速であることが実装している間、他の方法に比べて比較的よく行うように見えることがわかります。function shuffle(array) {
var random = array.map(Math.random);
array.sort(function(a, b) {
return random[array.indexOf(a)] - random[array.indexOf(b)];
});
}
indexOf
を使用する必要がある理由である、値ではなく、インデックスと呼ばれています。 indexOf
はO(N)時間で実行されるように、この変化は、より大きな配列のためのコードはあまり適したものとなることに注意してください。
は、シャッフル機能は変わらないソース配列
更新:私はこれが比較的 簡単な (ないから 複雑性 視点) 短 アルゴリズムがいっぱいで仕分けもバッチリでの微小さいサイズの配列が、レコード店ディスクユニオンの料金以上に多くのクラシック Durstenfeld アルゴリズムを相手にする時に巨大な配列.できます Durstenfeld 一つの回答がこの質問です。
独自の回答:
の場合 いないの おシャッフル機能の変異の ソース配列,それをコピーすることができますローカル変数、そのいの簡単な シャッフリングロジック.
function shuffle(array) {
var result = [], source = array.concat([]);
while (source.length) {
let index = Math.floor(Math.random() * source.length);
result.push(source[index]);
source.splice(index, 1);
}
return result;
}
シャッフリングロジック:お迎えにランダム指数、それに対応する要素の 結果の配列 削除してから ソース配列のコピー.これを繰り返し動作までのソース配列を取得す 空.
ましたので、こちらのどん:
function shuffle(array) {
var result = [], source = array.concat([]);
while (source.length) {
let index = Math.floor(Math.random() * source.length);
result.push(source.splice(index, 1)[0]);
}
return result;
}
さらに別の実施
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;
}
他のすべての答えはcryptgraphicレベルのランダム化に適した高速だがないMath.random()に基づいています。
無作為のの暗号化レベルのためFisher-Yates
を利用しながら、以下のコードは、周知Web Cryptography API
アルゴリズムを使用しています。
var d = [1,2,3,4,5,6,7,8,9,10];
function shuffle(a) {
var x, t, r = new Uint32Array(1);
for (var i = 0, c = a.length - 1, m = a.length; i < c; i++, m--) {
crypto.getRandomValues(r);
x = Math.floor(r / 65536 / 65536 * m) + i;
t = a [i], a [i] = a [x], a [x] = t;
}
return a;
}
console.log(shuffle(d));
の現代短いインライン溶液の
['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);
(教育目的のために)の
ただ、パイで指を持っています。ここで私は、フィッシャーイエーツシャッフル(と思う)の再帰的な実装を提示します。これは、均一なランダム性を与えます。
注:~~
(ダブルチルダ演算子は)実際には正の実数について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])));
元の配列を変更することはありませんCoolAJ86の回答するの簡単な修正ます:
/**
* Returns a new array whose contents are a shuffled copy of the original array.
* @param {Array} The items to shuffle.
* https://stackoverflow.com/a/2450976/1673761
* https://stackoverflow.com/a/44071316/1673761
*/
const shuffle = (array) => {
let currentIndex = array.length;
let temporaryValue;
let randomIndex;
const newArray = array.slice();
// While there remains elements to shuffle...
while (currentIndex) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// Swap it with the current element.
temporaryValue = newArray[currentIndex];
newArray[currentIndex] = newArray[randomIndex];
newArray[randomIndex] = temporaryValue;
}
return newArray;
};
がすでに助言が、私たちは、foreachループを使用して、それは短く、簡単に作ることができる感じの実装の数があるので、我々は、配列の長さを計算することを心配する必要はありませんし、また私たちが安全に一時的な変数の使用を避けることができますが。
var myArr = ["a", "b", "c", "d"];
myArr.forEach((val, key) => {
randomIndex = Math.ceil(Math.random()*(key + 1));
myArr[key] = myArr[randomIndex];
myArr[randomIndex] = val;
});
// see the values
console.log('Shuffled Array: ', myArr)
最短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;
}
理論的な観点からは、それを行うための最もエレガントな方法は、私の愚見では、の0 との間にのシングルの乱数を取得することですnは!-1 のと{0, 1, …, n!-1}
のすべての順列に(0, 1, 2, …, n-1)
から1対1のマッピングを計算します。限り、あなたはどんな大きな偏りなく、そのような番号を取得するための十分な信頼性の高い(擬似)乱数生成器を使用することができるように、あなたは他のいくつかの乱数を必要とせずに、あなたが望むものを達成するためにそれで十分な情報を持っています。
、あなたはあなたの乱数発生器は、約15小数を提供することを期待することができます。あなたは(13桁)の15!= 1,307,674,368,000 の持っているので、あなたは、15個の要素までを含む配列で、以下の機能を使用し、14個の要素までを含むアレイと有意な偏りが生じないと仮定することができます。このシャッフル操作時間の多くを計算するために必要な固定サイズの問題に取り組む場合、あなたはそれが一度だけMath.random
を使用しているため、が他のコードよりも速いかもしれを次のコードを試してみたいことがあります(これには、いくつかの関係しますコピー操作が)。
以下の機能は使用できませんが、私はとにかくそれを与えます。それは、このメッセージ(permuationsを列挙最も自然なもの)に使用される1つのマッピングの一項に記載の(0, 1, 2, …, n-1)
の所与の順列のインデックスを返します。最大16個の要素で動作するように意図されます:
function permIndex(p) {
var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
var tail = [];
var i;
if (p.length == 0) return 0;
for(i=1;i<(p.length);i++) {
if (p[i] > p[0]) tail.push(p[i]-1);
else tail.push(p[i]);
}
return p[0] * fact[p.length-1] + permIndex(tail);
}
(ご自身の質問のために必要な)前の関数の逆数は以下の通りです。最大16個の要素で動作するように意図されます。それは順序の順列を返します。のN の(0, 1, 2, …, s-1)
のます:
function permNth(n, s) {
var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
var i, j;
var p = [];
var q = [];
for(i=0;i<s;i++) p.push(i);
for(i=s-1; i>=0; i--) {
j = Math.floor(n / fact[i]);
n -= j*fact[i];
q.push(p[j]);
for(;j<i;j++) p[j]=p[j+1];
}
return q;
}
さて、あなたは単に欲しいのです。
function shuffle(p) {
var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000];
return permNth(Math.floor(Math.random()*fact[p.length]), p.length).map(
function(i) { return p[i]; });
}
これは、ほとんど理論的なバイアス(実用的な観点から目立たないが)で最大16個の要素のために働くべきです。それは15個の要素のために完全に使用可能と見なすことができます。 14個の未満の要素を含む配列で、あなたは安全に全く偏りがないだろうと考えることができます。
おかしい十分に全く非変異再帰的な答えはありませんでした。
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("What?",JSON.stringify(arr))
if(currentIndex===0){
return arr;
}
const randomIndex = Math.floor(Math.random() * currentIndex);
const swap = arr[currentIndex];
arr[currentIndex] = arr[randomIndex];
arr[randomIndex] = swap;
return recur(
arr,
currentIndex - 1
);
}
return recur(arr.map(x=>x),arr.length-1);
};
var arr = [1,2,3,4,5,[6]];
console.log(shuffle(arr));
console.log(arr);
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;
}
array.spliceを使用してアレイをランダム()
function shuffleArray(array) {
var temp = [];
var len=array.length;
while(len){
temp.push(array.splice(Math.floor(Math.random()*array.length),1)[0]);
len--;
}
return temp;
}
//console.log("Here >>> "+shuffleArray([4,2,3,5,8,1,0]));