Pertanyaan Bagaimana cara mengacak (mengacak) susunan JavaScript?


Saya memiliki larik seperti ini:

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

Bagaimana saya bisa mengacak / mengacaknya?


872
2018-03-15 22:37


asal


Jawaban:


Algoritma shuffle de-facto yang tidak bias adalah Fisher-Yates (alias Knuth) Shuffle.

Lihat https://github.com/coolaj86/knuth-shuffle

Anda dapat melihat a visualisasi yang bagus di sini (dan posting asli terkait dengan ini)

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);

Beberapa info lagi tentang algoritma bekas.


1084
2017-09-28 20:20



Berikut ini adalah implementasi JavaScript dari Durstenfeld shuffle, versi Fisher-Yates yang dioptimalkan untuk komputer:

/**
 * 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;
    }
}

Algoritme Fisher-Yates bekerja dengan memilih satu elemen acak untuk setiap elemen array asli, dan kemudian mengecualikannya dari undian berikutnya. Sama seperti memilih secara acak dari setumpuk kartu.

Pengecualian ini dilakukan dengan cara cerdas (diciptakan oleh Durstenfeld untuk digunakan oleh komputer) dengan menukar elemen yang dipilih dengan elemen saat ini, dan kemudian memilih elemen acak berikutnya dari sisanya. Untuk efisiensi optimal, loop berjalan mundur sehingga pick acak disederhanakan (selalu dapat dimulai pada 0), dan melewatkan elemen terakhir karena tidak ada pilihan lain lagi.

Waktu berjalan dari algoritma ini adalah O (n). Perhatikan bahwa shuffle dilakukan di tempat. Jadi jika Anda tidak ingin mengubah array asli, buatlah salinannya terlebih dahulu dengan .slice(0).

Memperbarui ke ES6 / ECMAScript 2015

ES6 baru memungkinkan kita untuk menetapkan dua variabel sekaligus. Ini sangat berguna ketika kita ingin menukar nilai dari dua variabel, seperti yang bisa kita lakukan dalam satu baris kode. Berikut ini adalah bentuk lebih pendek dari fungsi yang sama, menggunakan fitur ini.

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]]; // eslint-disable-line no-param-reassign
    }
}

477
2017-09-06 04:55



[pengeditan komunitas: Jawaban ini salah; lihat komentar. Itu ditinggalkan di sini untuk referensi di masa mendatang karena idenya tidak begitu langka.]

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});

85
2018-04-13 13:59



Seseorang dapat (atau seharusnya) menggunakannya sebagai protoype dari Array:

Dari ChristopheD:

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;
}

69
2018-03-31 05:29



Gunakan pustaka underscore.js. Metode _.shuffle() bagus untuk kasus ini. Berikut ini contoh dengan metode:

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();

56
2017-09-22 23:21



BARU!

Lebih pendek & mungkin * lebih cepat algoritma shuffle Fisher-Yates

  1. itu menggunakan sementara ---
  2. bitwise to floor (angka hingga 10 digit desimal (32bit))
  3. menghapus penutupan yang tidak perlu & hal-hal lain

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
}

ukuran skrip (dengan fy sebagai nama fungsi): 90bytes

DEMO http://jsfiddle.net/vvpoma8w/

* lebih cepat mungkin di semua browser kecuali chrome.

Jika Anda memiliki pertanyaan, tanyakan saja.

EDIT

ya itu lebih cepat

KINERJA:  http://jsperf.com/fyshuffle

menggunakan bagian atas memilih fungsi.

EDIT  Ada perhitungan yang berlebihan (tidak perlu --c + 1) dan tidak ada yang memperhatikan

lebih pendek (4 byte) & lebih cepat (ujilah!).

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
}

Menyimpan di tempat lain var rnd=Math.random lalu gunakan rnd() juga akan meningkatkan sedikit kinerja pada array besar.

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

Versi yang dapat dibaca (gunakan versi asli. ini lebih lambat, vars tidak berguna, seperti penutup & ";", kode itu sendiri juga lebih pendek ... mungkin baca ini Bagaimana cara 'mengecilkan' kode Javascript , btw Anda tidak dapat mengompres kode berikut dalam minifiers javascript seperti yang di atas.)

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
 }
}

45
2018-04-05 15:38



Cara yang sangat sederhana untuk array kecil hanyalah ini:

const someArray = [1, 2, 3, 4, 5];

someArray.sort(() => Math.random() - 0.5);

Ini mungkin tidak sangat efisien, tetapi untuk array kecil ini bekerja dengan baik. Berikut ini contohnya sehingga Anda dapat melihat seberapa acak (atau tidak) itu, dan apakah itu sesuai dengan usecase Anda atau tidak.

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>


23
2017-10-03 13:16



Anda dapat melakukannya dengan mudah dengan peta dan mengurutkan:

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)
  1. Kami menempatkan setiap elemen dalam array dalam suatu objek, dan memberikannya kunci sortir acak
  2. Kami mengurutkan menggunakan kunci acak
  3. Kami unmap untuk mendapatkan objek asli

Anda dapat mengacak susunan polimorfik, dan semacamnya acak seperti Math.random, yang cukup baik untuk sebagian besar tujuan.

Karena elemen disortir terhadap kunci konsisten yang tidak diregenerasi setiap iterasi, dan setiap perbandingan menarik dari distribusi yang sama, setiap non-acak dalam distribusi Math.random dibatalkan.


23
2018-04-01 21:23