Bagaimana cara mengacak (mengocok) array JavaScript?

1266

Saya memiliki array seperti ini:

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

Bagaimana saya bisa mengacak / mengacaknya?

Klik Upvote
sumber
6
Hanya melemparkan ini di sini bahwa Anda dapat memvisualisasikan bagaimana acak fungsi mengocok sebenarnya dengan visualisator ini Mike Bostock membuat: bost.ocks.org/mike/shuffle/compare.html
Agustus
5
@Blazemonger jsPref sudah mati. Bisakah Anda memposting di sini mana yang tercepat?
eozzy
Bagaimana dengan one-liner? Array yang dikembalikan dikocok. arr1.reduce ((a, v) => a.splice (Math.floor (Math.random () * a.length), 0, v) && a, [])
brunettdan
Solusi pengurangan memiliki kompleksitas O (n ^ 2). Coba jalankan pada array dengan sejuta elemen.
riv

Jawaban:

1542

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

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

Anda dapat melihat visualisasi yang hebat di sini (dan pos asli yang ditautkan 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];
shuffle(arr);
console.log(arr);

Beberapa info lebih lanjut tentang algoritma yang digunakan.

CoolAJ86
sumber
13
Jawaban di atas melewatkan elemen 0, kondisinya seharusnya i--tidak --i. Juga, tes if (i==0)...ini berlebihan karena jika i == 0itu sementara lingkaran akan pernah masuk. Panggilan ke Math.floordapat dilakukan dengan lebih cepat menggunakan ...| 0. Baik tempi atau tempj dapat dihapus dan nilainya langsung ditugaskan ke myArray [i] atau j yang sesuai.
RobG
23
@prometheus, semua RNG adalah pseudo-acak kecuali terhubung ke perangkat keras yang mahal.
Phil H
38
@RobG implementasi di atas benar secara fungsional. Dalam algoritma Fisher-Yates, loop tidak dimaksudkan untuk berjalan untuk elemen pertama dalam array. Lihat wikipedia di mana ada implementasi lain yang juga melewatkan elemen pertama. Lihat juga artikel ini yang membahas tentang mengapa loop penting untuk tidak berjalan untuk elemen pertama.
theon
34
@nikola "tidak acak sama sekali" adalah kualifikasi yang sedikit kuat bagi saya. Saya berpendapat bahwa itu cukup acak kecuali Anda seorang cryptographer, dalam hal ini Anda mungkin tidak menggunakan Math.Random () di tempat pertama.
toon81
20
Ugh, yoda ( 0 !== currentIndex).
ffxsam
746

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

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

Ini mengambil elemen acak untuk setiap elemen array asli, dan mengecualikannya dari undian berikutnya, seperti memilih secara acak dari setumpuk kartu.

Pengecualian pintar ini menukar elemen yang dipilih dengan elemen saat ini, kemudian mengambil elemen acak berikutnya dari sisanya, mengulang ke belakang untuk efisiensi optimal, memastikan pengambilan acak disederhanakan (selalu dapat mulai dari 0), dan dengan demikian melewatkan elemen terakhir.

Algoritma runtime adalah O(n). Perhatikan bahwa pengocokan dilakukan di tempat jadi jika Anda tidak ingin memodifikasi array asli, pertama-tama buat salinannya .slice(0).


EDIT: 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, karena kita dapat melakukannya dalam satu baris kode. Ini adalah bentuk yang 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]];
    }
}
Laurens Holst
sumber
22
ps Algoritma yang sama dengan jawaban ChristopheD, tetapi dengan penjelasan dan implementasi yang lebih bersih.
Laurens Holst
12
Orang menghubungkan orang yang salah untuk algoritma. Ini bukan Fisher-Yates shuffle, melainkan Durstenfeld shuffle . Algoritma Fisher-Yates asli yang asli berjalan dalam waktu n ^ 2, bukan waktu
Pacerier
7
Tidak perlu return arraykarena JavaScript melewati array dengan referensi ketika digunakan sebagai argumen fungsi. Saya berasumsi ini untuk menghemat ruang stack, tapi ini fitur kecil yang menarik. Melakukan shuffle pada array akan mengocok array asli.
Joel Trauger
5
Implementasi dalam jawaban ini mendukung ujung bawah array. Menemukan cara yang sulit . Math.random() should not be multiplied with the loop counter + 1, but with array.lengt () `. Lihat Menghasilkan bilangan bulat acak dalam JavaScript dalam rentang tertentu? untuk penjelasan yang sangat komprehensif.
Marjan Venema
13
@MarjanVenema Tidak yakin apakah Anda masih menonton ruang ini, tetapi jawaban ini benar, dan perubahan yang Anda sarankan benar-benar menimbulkan bias. Lihat blog.codinghorror.com/the-danger-of-naivete untuk penulisan kesalahan ini.
user94559
134

Peringatan!
Penggunaan algoritma ini tidak disarankan , karena tidak efisien dan sangat bias ; lihat komentar. Itu ditinggalkan di sini untuk referensi di masa depan, karena idenya tidak terlalu langka.

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});
deadrunk
sumber
13
Saya suka solusi ini, cukup untuk memberikan dasar acak
Alex K
147
Menunduk karena ini tidak benar-benar acak. Saya tidak tahu mengapa ada begitu banyak upvotes. Jangan gunakan metode ini. Itu terlihat cantik, tetapi tidak sepenuhnya benar. Berikut adalah hasil setelah 10.000 iterasi pada berapa kali setiap angka dalam indeks hits array Anda [0] (Saya dapat memberikan hasil lainnya juga): 1 = 29,19%, 2 = 29,53%, 3 = 20,06%, 4 = 11,91%, 5 = 5,99%, 6 = 3,32%
radtad
8
Tidak apa-apa jika Anda perlu mengacak array yang relatif kecil dan tidak berurusan dengan hal-hal kriptografi. Saya sepenuhnya setuju bahwa jika Anda membutuhkan lebih banyak keacakan, Anda perlu menggunakan solusi yang lebih kompleks.
deadrunk
12
Masalahnya adalah itu tidak deterministik, yang akan memberikan hasil yang salah (jika 1> 2 dan 2> 3, itu harus diberikan bahwa 1> 3, tetapi ini tidak akan menjamin itu. Ini akan mengacaukan penyortiran, dan memberikan hasil berkomentar oleh @radtad).
MatsLindh
73

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;
}
menipu
sumber
42
Benar-benar tidak ada manfaatnya, IMOHO, kecuali mungkin menginjak implementasi orang lain ..
user2864740
2
Jika digunakan dalam prototipe Array, itu harus dinamai bukan hanya acak .
Wolf,
57
Seseorang dapat (atau harus) menghindari memperpanjang Prototipe Asli: javascriptweblog.wordpress.com/2011/12/12/05 ...
Wédney Yuri
12
Anda seharusnya tidak melakukan ini; setiap larik tunggal yang terpengaruh oleh ini tidak lagi dapat diulang menggunakan dengan aman untuk ... di. Jangan memperluas prototipe asli.
18
@TinyGiant Sebenarnya: jangan gunakan for...inloop untuk beralih di atas array.
Conor O'Brien
69

Anda dapat melakukannya dengan mudah dengan memetakan 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 di objek, dan memberikannya kunci pengurutan acak
  2. Kami mengurutkan menggunakan kunci acak
  3. Kami menghapus peta untuk mendapatkan objek asli

Anda dapat mengocok array polimorfik, dan pengurutannya acak seperti Math.random, yang cukup baik untuk sebagian besar tujuan.

Karena elemen diurutkan berdasarkan kunci konsisten yang tidak dibuat ulang setiap iterasi, dan setiap perbandingan menarik dari distribusi yang sama, setiap non-keacakan dalam distribusi Math.random dibatalkan.

Kecepatan

Kompleksitas waktu adalah O (N log N), sama dengan quick sort. Kompleksitas ruang adalah O (N). Ini tidak seefisien shuffle Fischer Yates tetapi, menurut saya, kode ini secara signifikan lebih pendek dan lebih fungsional. Jika Anda memiliki array besar, Anda tentu harus menggunakan Fischer Yates. Jika Anda memiliki array kecil dengan beberapa ratus item, Anda dapat melakukan ini.

superluminary
sumber
1
@superluminary Ups, Anda benar. Perhatikan bahwa jawaban ini sudah menggunakan pendekatan yang sama.
Bergi
@Bergi - Ah ya, Anda benar, meskipun saya pikir implementasi saya sedikit lebih cantik.
superluminary
3
Sangat bagus. Ini adalah transformasi Schwartzian pada js.
Mark Grimes
@torazaburo - Ini tidak sebagus Fischer Yates, tapi lebih cantik dan kodenya lebih kecil. Kode selalu merupakan trade-off. Jika saya memiliki array yang besar, saya akan menggunakan Knuth. Jika saya punya beberapa ratus item, saya akan melakukan ini.
superluminary
1
@ BenCarp - Setuju, Ini bukan solusi tercepat dan Anda tidak ingin menggunakannya pada array besar, tetapi ada lebih banyak pertimbangan dalam kode daripada kecepatan mentah.
superluminary
64

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

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();
vn_grv
sumber
12
Jawaban bagus! Terima kasih. Saya lebih suka itu daripada jawaban lain, karena mendorong orang untuk menggunakan perpustakaan daripada menyalin dan menempel fungsi yang berpotensi bermasalah di mana-mana.
frabcus
60
@frabcus: Tidak ada gunanya menyertakan seluruh perpustakaan hanya untuk mendapatkan shufflefungsi.
Blender
11
Saya tidak setuju dengan @Blender. Ada banyak alasan untuk menyertakan seluruh perpustakaan hanya untuk mendapatkan fungsi yang Anda butuhkan. Salah satunya adalah risiko bug yang berkurang saat Anda menulisnya sendiri. Jika ini masalah kinerja, maka Anda seharusnya tidak menggunakannya. Tetapi hanya karena itu bisa menjadi masalah kinerja bukan berarti itu akan terjadi.
Daniel Kaplan
7
@tieTYT: Jadi mengapa Anda perlu perpustakaan lainnya? Shuffle Fisher-Yates sepele untuk diterapkan. Anda tidak perlu perpustakaan untuk memilih elemen acak dari array (saya harap), jadi tidak ada alasan untuk menggunakan perpustakaan kecuali Anda benar-benar akan menggunakan lebih dari satu fungsi darinya.
Blender
18
@Blender: Saya memberi alasan mengapa. 1) Saya yakinkan Anda, Anda dapat memperkenalkan bug ke dalam kode apa pun yang Anda tulis, tidak peduli seberapa sepele itu. Mengapa mengambil risiko itu? 2) Jangan melakukan pra-optimisasi. 3) 99% saat Anda membutuhkan shuffle algo, aplikasi Anda bukan tentang menulis shuffle algo. Ini tentang sesuatu yang membutuhkan algo shuffle. Leverage karya orang lain. Jangan memikirkan detail implementasi kecuali Anda harus melakukannya.
Daniel Kaplan
50

BARU!

Algoritma shuffle Fisher-Yates lebih pendek & mungkin lebih cepat

  1. ini digunakan saat ---
  2. bitwise ke lantai (angka hingga 10 angka 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 fungsi terpilih teratas.

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

lebih pendek (4bytes) & lebih cepat (coba!)

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
}

Caching di tempat lain var rnd=Math.randomlalu gunakanrnd() juga akan sedikit meningkatkan kinerja pada array besar.

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

Versi yang dapat dibaca (gunakan versi asli. Ini lebih lambat, vars tidak berguna, seperti penutupan & ";", kode itu sendiri juga lebih pendek ... mungkin baca ini Cara 'memperkecil' kode Javascript , tetapi Anda tidak dapat kompres 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
 }
}
cocco
sumber
6
lihat kinerjanya ... 2x lebih cepat di sebagian besar browser ... tetapi perlu lebih banyak penguji jsperf ...
cocco
10
js adalah bahasa yang menerima banyak pintasan dan berbagai cara untuk menulisnya .. sementara ada banyak fungsi yang dapat dibaca lambat di sini saya hanya ingin menunjukkan bagaimana itu bisa dilakukan dengan cara yang lebih performan, juga menghemat beberapa byte ... bitwise dan singkatan benar-benar diremehkan di sini dan web penuh dengan kode kereta dan lambat.
cocco
Bukan peningkatan slam dunk perf. Mengganti fydan shuffle prototype, saya mendapatkan fysecara konsisten di bagian bawah di Chrome 37 pada OS X 10.9.5 (81% lebih lambat ~ 20k ops dibandingkan dengan ~ 100k) dan Safari 7.1 itu hingga ~ 8% lebih lambat. YMMV, tapi itu tidak selalu lebih cepat. jsperf.com/fyshuffle/3
Spig
periksa statistik lagi ... saya sudah menulis chrome lebih lambat karena mereka dioptimalkan Matematika, di semua lantai bitwise dan sementara lebih cepat. periksa IE, firefox tetapi juga perangkat seluler. Menyenangkan juga melihat opera ...
cocco
1
Ini jawaban yang mengerikan. SO bukan kompetisi yang mengaburkan.
Puppy
39

Sunting: Jawaban ini salah

Lihat komentar dan https://stackoverflow.com/a/18650169/28234 . Itu ditinggalkan di sini untuk referensi karena idenya tidak jarang.


Cara yang sangat sederhana untuk array kecil adalah ini:

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

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

Ini mungkin tidak terlalu efisien, tetapi untuk array kecil ini berfungsi dengan baik. Berikut ini contoh sehingga Anda dapat melihat seberapa acak (atau tidak) itu, dan apakah itu cocok dengan usecase 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>

Kris Selbekk
sumber
Bagus, tetapi apakah menghasilkan elemen acak lengkap setiap saat?
DDD
Tidak yakin apakah saya mengerti Anda dengan benar. Pendekatan ini memang akan mengocok array dengan cara acak (meskipun pseudo-acak) setiap kali Anda memanggil array semacam - itu bukan jenis yang stabil, karena alasan yang jelas.
Kris Selbekk
4
Untuk alasan yang sama seperti yang dijelaskan di stackoverflow.com/a/18650169/28234 . Ini jauh lebih memungkinkan untuk meninggalkan elemen awal di dekat awal array.
AlexC
7
Ini sangat bagus, mudah untuk digunakan ketika Anda perlu mengaduk array, tetapi tidak terlalu peduli untuk memiliki hasil yang acak secara akademis. Terkadang, beberapa inci terakhir menuju kesempurnaan membutuhkan waktu lebih lama daripada nilainya.
Daniel Griscom
1
Akan menyenangkan jika ini berhasil, tetapi tidak. Karena cara pencarian cepat berfungsi, pembanding yang tidak konsisten akan cenderung meninggalkan elemen array dekat dengan posisi aslinya. Array Anda tidak akan diacak.
superluminary
39

Andal, Efisien, Pendek

Beberapa solusi pada halaman ini tidak dapat diandalkan (mereka hanya mengacak sebagian array). Solusi lain secara signifikan kurang efisien. DengantestShuffleArrayFun (lihat di bawah) kami dapat menguji fungsi pengocokan array untuk keandalan dan kinerja. Solusi berikut adalah: dapat diandalkan, efisien dan pendek (menggunakan sintaks ES6)

[Pengujian perbandingan dilakukan dengan menggunakan testShuffleArrayFunsolusi lain, di Google Chrome]

Shuffle Array In place

    function getShuffledArr (array){
        for (var i = array.length - 1; i > 0; i--) {
            var rand = Math.floor(Math.random() * (i + 1));
            [array[i], array[rand]] = [array[rand], array[i]]
        }
    }

ES6 Murni, Berulang

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

Uji Reliabilitas dan Kinerja

Seperti yang Anda lihat di halaman ini, ada solusi yang salah yang ditawarkan di sini di masa lalu. Saya menulis dan telah menggunakan fungsi berikut untuk menguji fungsi pengacakan array murni (tanpa efek samping).

    function testShuffleArrayFun(getShuffledArrayFun){
        const arr = [0,1,2,3,4,5,6,7,8,9]

        var 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 (var i=0 ; i<n ; i++){
            //   We'll call getShuffledArrayFun n times. 
            //   And for each iteration, we'll increment the counter. 
            var 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}`)
    }

Solusi Lain

Solusi lain hanya untuk bersenang-senang.

ES6 Murni, Rekursif

    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 Pure menggunakan array.map

    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 Pure menggunakan array.reduce

    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]
        )
    }
Ben Carp
sumber
Jadi, di mana ES6 (ES2015)? [array[i], array[rand]]=[array[rand], array[i]]? Mungkin Anda bisa menguraikan cara kerjanya. Mengapa Anda memilih untuk beralih ke bawah?
sheriffderek
@ Sheriffderek Ya, fitur ES6 yang saya gunakan adalah penugasan dua vars sekaligus, yang memungkinkan kita untuk menukar dua vars dalam satu baris kode.
Ben Carp
Kredit untuk @sheriffderek yang menyarankan Algoritma naik. Algoritma naik dapat dibuktikan dalam induksi.
Ben Carp
23

Menambahkan ke jawaban @Laurens Holsts. Ini dikompresi 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
};
KingKongFrog
sumber
3
Kita harus mendorong orang untuk menggunakan _.shuffle daripada menempelkan kode dari stack overflow; dan, kita harus mengecilkan hati orang dari mengompresi jawaban stack overflow mereka. Itulah gunanya jsmin.
David Jones
45
@ DavidJones: Mengapa saya harus menyertakan seluruh perpustakaan 4kb hanya untuk mengocok array?
Blender
1
Pemanggilan nama @KingKongFrog juga tidak konduktif untuk kumpulan komunitas yang masuk akal.
wheaties
2
Apakah efisien untuk dilakukan var b = dalam satu lingkaran daripada mendeklarasikan b di luar lingkaran dan menugaskannya b = dalam satu lingkaran?
Alex K
2
@ Brian Tidak akan membuat perbedaan; pengangkatan terjadi ketika kode sumber diuraikan. Tidak mungkin terlibat.
user2864740
23

Sunting: Jawaban ini salah

Lihat https://stackoverflow.com/a/18650169/28234 . Itu ditinggalkan di sini untuk referensi karena idenya tidak jarang.

//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 adalah angka acak yang mungkin positif atau negatif, sehingga fungsi pengurutan akan menata ulang elemen secara acak.

hakiko
sumber
17

Dengan ES2015 Anda dapat menggunakan ini:

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

Pemakaian:

[1, 2, 3, 4, 5, 6, 7].shuffle();
BrunoLM
sumber
4
Untuk truncate, Anda harus menggunakan n >>> 0bukan ~~n. Indeks array bisa lebih tinggi dari 2³¹-1.
Oriol
1
Destrukturisasi seperti ini membuat implementasi bersih +1
lukejacksonn
14

Saya menemukan varian ini nongkrong di jawaban "dihapus oleh penulis" pada duplikat dari pertanyaan ini. Tidak seperti beberapa jawaban lain yang sudah memiliki banyak upvotes, ini adalah:

  1. Sebenarnya acak
  2. Tidak di tempat (karena itu shufflednamanya, bukan shuffle)
  3. Belum hadir di sini dengan beberapa varian

Ini jsfiddle yang menunjukkan sedang digunakan .

Array.prototype.shuffled = function() {
  return this.map(function(n){ return [Math.random(), n] })
             .sort().map(function(n){ return n[1] });
}
Daniel Martin
sumber
(Saya menduga itu telah dihapus karena ini adalah cara yang sangat tidak efisien untuk mengacak array, terutama untuk array yang lebih besar ... sedangkan jawaban yang diterima, dan sejumlah klon lain dari jawaban itu mengacak di tempat).
WiredPrairie
1
Ya, tetapi mengingat bahwa jawaban yang salah yang terkenal masih dengan banyak suara, solusi yang tidak efisien tetapi benar setidaknya harus disebutkan.
Daniel Martin
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });- tidak memberikan penyortiran acak, dan jika Anda menggunakannya, Anda bisa merasa malu: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
Daniel Martin
3
Anda perlu menggunakan .sort(function(a,b){ return a[0] - b[0]; })jika Anda ingin menyortir untuk membandingkan nilai secara numerik. .sort()Komparator default adalah leksikografis, artinya akan dianggap 10kurang dari 2karena 1kurang dari 2.
4castle
@ 4castle Oke, saya memperbarui kode, tetapi saya akan mengembalikannya: perbedaan antara urutan leksikografis dan urutan numerik tidak masalah untuk angka dalam rentang yang Math.random()menghasilkan. (yaitu, urutan leksikografis sama dengan urutan numerik ketika berhadapan dengan angka dari 0 (inklusif) hingga 1 (eksklusif))
Daniel Martin
14
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;
};
Tophe
sumber
Ini jelas tidak seoptimal algoritma Fisher-Yates, tetapi apakah itu akan bekerja untuk wawancara teknis?
davidatthepark
@Andrea Kode rusak karena fakta bahwa panjang array diubah di dalam for loop. Dengan pengeditan terakhir ini diperbaiki.
Charlie Wallace
12
arr1.sort(() => Math.random() - 0.5);
Sam Doidge
sumber
1
Mengapa minus 0,5? Apa arti angka itu?
Sartheris Stormhammer
1
@SartherisStormhammer karena kami menggunakan fungsi Perbandingan untuk, dan jika itu mengembalikan angka lebih besar dari 0, elemen yang dibandingkan akan dipesan dalam arah saja. -0,5 pada Math.random () akan memberi kita angka negatif ~ 50% dari waktu, yang memberi kita urutan terbalik.
Sam Doidge
Solusi lurus ke depan dan paling sederhana. Terima kasih
deanwilliammills
9

Anda dapat melakukannya dengan mudah dengan:

// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);

Silakan referensi di Array Penyortiran JavaScript

Tính Ngô Quang
sumber
Algoritma ini telah lama terbukti cacat.
Tolong buktikan kepada saya. Saya berdasarkan pada w3schools
Tính Ngô Quang
4
Anda dapat membaca utas di css-tricks.com/snippets/javascript/shuffle-array , atau di news.ycombinator.com/item?id=2728914 . W3sekolah selalu menjadi, dan tetap, sumber informasi yang mengerikan.
Untuk diskusi yang baik tentang mengapa ini bukan pendekatan yang baik lihat stackoverflow.com/questions/962802/…
Charlie Wallace
8

Solusi rekursif:

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));
};
Julian
sumber
8

Fisher-Yates mengacak dalam javascript. Saya memposting ini di sini karena penggunaan dua fungsi utilitas (swap dan randInt) memperjelas algoritme dibandingkan dengan jawaban lain di sini.

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);
  }
}
Daniel Patru
sumber
7

Pertama-tama, lihat di sini untuk perbandingan visual yang bagus dari berbagai metode penyortiran dalam javascript.

Kedua, jika Anda melihat sekilas tautan di atas, Anda akan menemukan bahwa random orderpengurutan tersebut tampaknya berkinerja relatif baik dibandingkan dengan metode lain, sementara sangat mudah dan cepat untuk diterapkan seperti yang ditunjukkan di bawah ini:

function shuffle(array) {
  var random = array.map(Math.random);
  array.sort(function(a, b) {
    return random[array.indexOf(a)] - random[array.indexOf(b)];
  });
}

Sunting : seperti yang ditunjukkan oleh @gregers, fungsi membandingkan disebut dengan nilai daripada indeks, itulah sebabnya Anda perlu menggunakan indexOf. Perhatikan bahwa perubahan ini membuat kode kurang cocok untuk array yang lebih besar karena indexOfberjalan dalam waktu O (n).

Milo Wielondek
sumber
Array.prototype.sortmelewati dua nilai sebagai adan b, bukan indeks. Jadi kode ini tidak berfungsi.
gregers
@regers Anda benar, saya sudah mengedit jawabannya. Terima kasih.
Milo Wielondek
1
Ini tidak terlalu acak. Bergantung pada penerapan pengurutan, elemen pada indeks array terendah mungkin memerlukan lebih banyak perbandingan untuk mendapatkan indeks tertinggi dari elemen di sebelah indeks tertinggi. Ini berarti bahwa kecil kemungkinan elemen pada indeks terendah mencapai indeks tertinggi.
1 'ATAU 1 -
7

fungsi acak yang tidak mengubah larik sumber

Pembaruan : Di sini saya menyarankan algoritma yang relatif sederhana (bukan dari perspektif kompleksitas ) dan pendek yang akan baik-baik saja dengan array berukuran kecil, tapi itu pasti akan jauh lebih mahal daripada algoritma Durstenfeld klasik ketika Anda berurusan dengan array besar. Anda dapat menemukan Durstenfeld di salah satu balasan teratas untuk pertanyaan ini.

Jawaban asli:

Jika Anda tidak ingin fungsi shuffle Anda untuk mengubah array sumber , Anda dapat menyalinnya ke variabel lokal, lalu lakukan sisanya dengan logika pengocokan sederhana .

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

Logika pengocokan : ambil indeks acak, lalu tambahkan elemen yang sesuai ke array hasil dan hapus dari salinan array sumber . Ulangi tindakan ini sampai array sumber menjadi kosong .

Dan jika Anda benar-benar menginginkannya pendek, berikut ini sejauh yang bisa saya dapatkan:

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;
}
Evgenia Manolova
sumber
Ini pada dasarnya adalah algoritma Fisher-Yates asli, dengan Anda splicemenjadi cara yang sangat tidak efisien untuk melakukan apa yang mereka sebut "mencolokkan". Jika Anda tidak ingin mengubah array asli, salin saja, lalu kocok salinan itu menggunakan varian Durstenfeld yang jauh lebih efisien.
@torazaburo, terima kasih atas tanggapan Anda. Saya telah memperbarui jawaban saya, untuk memperjelas bahwa saya agak menawarkan solusi yang terlihat bagus, daripada solusi super-skala
Evgenia Manolova
Kami juga bisa menggunakan splicemetode untuk membuat salinan seperti: source = array.slice();.
Taiga
6

Inilah yang TERMUDAH ,

function shuffle(array) {
  return array.sort(() => Math.random() - 0.5);
}

untuk contoh lebih lanjut, Anda dapat memeriksanya di sini

Aljohn Yamaro
sumber
5

Belum lagi implementasi Fisher-Yates, menggunakan mode ketat:

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;
}
Raphael C
sumber
Nilai apa yang diberikan penambahan penggunaan yang ketat atas jawaban yang diterima?
shortstuffsushi
Untuk mempelajari lebih lanjut tentang mode ketat dan bagaimana hal itu mempengaruhi kinerja Anda dapat membacanya di sini: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
Raphael C
Hmm, bisakah Anda menunjuk sesuatu yang spesifik dari dokumen yang dirujuk? Tidak ada di sana tampaknya merujuk "meningkatkan kinerja," selain dari komentar samar di atas tentang berpotensi menyulitkan mesin js untuk mengoptimalkan. Dalam hal ini, tidak jelas bagi saya apa yang akan meningkatkan penggunaan ketat.
shortstuffsushi
Mode ketat telah ada selama beberapa waktu, dan ada cukup banyak bacaan di luar sana bagi siapa pun untuk membuat pendapat mereka sendiri jika mereka harus selalu menggunakannya atau tidak dan mengapa. Jslint misalnya membuatnya cukup jelas sehingga Anda harus selalu menggunakan mode ketat. Douglas Crockford telah menulis cukup banyak artikel dan beberapa video hebat tentang mengapa penting untuk selalu menggunakan mode ketat tidak hanya sebagai praktik yang baik tetapi juga bagaimana hal itu ditafsirkan secara berbeda oleh mesin js browser seperti V8. Saya sangat menyarankan Anda untuk Google dan membuat pendapat Anda sendiri tentang hal itu.
Raphael C
Berikut ini adalah utas lama tentang perf dalam mode ketat, agak tua tetapi masih relevan: stackoverflow.com/questions/3145966/…
Raphael C
5

Semua jawaban lain didasarkan pada Math.random () yang cepat tetapi tidak cocok untuk pengacakan tingkat cryptgraphic.

Kode di bawah ini menggunakan terkenal Fisher-Yatesalgoritma sambil memanfaatkan Web Cryptography APIuntuk tingkat kriptografi pengacakan .

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

Marcin Malinowski
sumber
4

Solusi inline pendek modern menggunakan fitur ES6:

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

(untuk tujuan pendidikan)

icl7126
sumber
4

Modifikasi sederhana dari jawaban CoolAJ86 yang tidak mengubah array asli:

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

Meskipun ada beberapa implementasi yang sudah disarankan tetapi saya merasa kita bisa membuatnya lebih pendek dan lebih mudah menggunakan forEach loop, jadi kita tidak perlu khawatir tentang menghitung panjang array dan juga kita bisa dengan aman menghindari menggunakan variabel sementara.

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)
Hafizur Rahman
sumber
4

Hanya untuk memiliki jari di pai. Di sini saya menyajikan implementasi rekursif shuffle Fisher Yates (saya pikir). Ini memberikan keacakan seragam.

Catatan: ~~(operator tilde ganda) sebenarnya berperilaku seperti Math.floor()untuk bilangan real positif. Hanya jalan pintas.

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

Sunting: Kode di atas adalah O (n ^ 2) karena penggunaan .splice()tetapi kita bisa menghilangkan splice dan shuffle di O (n) dengan trik swap.

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

Masalahnya, JS tidak bisa bekerja sama dengan rekursi besar. Dalam kasus khusus ini Anda ukuran array dibatasi dengan seperti 3000 ~ 7000 tergantung pada mesin browser Anda dan beberapa fakta yang tidak diketahui.

Redu
sumber
3

Mengacak array

 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; 
vickisys
sumber
Seharusnya tidak ada -1untuk n seperti yang Anda <tidak gunakan<=
Mohebifar
3

arrayShufflefungsi terpendek

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;
}
Tusko Trush
sumber
Tampaknya Anda melakukan Sattolo's bukannya Fisher-Yates (Knuth, tidak memihak).
Arthur2e5
3

Dari sudut pandang teoretis, cara paling elegan untuk melakukannya, menurut pendapat saya, adalah untuk mendapatkan nomor acak tunggal antara 0 dan n! -1 dan untuk menghitung pemetaan satu ke satu dari {0, 1, …, n!-1}semua permutasi dari(0, 1, 2, …, n-1) . Selama Anda dapat menggunakan generator acak (pseudo-) yang cukup andal untuk mendapatkan nomor seperti itu tanpa bias yang berarti, Anda memiliki informasi yang cukup di dalamnya untuk mencapai apa yang Anda inginkan tanpa memerlukan beberapa nomor acak lainnya.

Saat menghitung dengan angka mengambang presisi ganda IEEE754, Anda dapat mengharapkan generator acak Anda untuk memberikan sekitar 15 desimal. Karena Anda memiliki 15! = 1.307.674.368.000 (dengan 13 digit), Anda dapat menggunakan fungsi berikut dengan array yang berisi hingga 15 elemen dan menganggap tidak akan ada bias signifikan dengan array yang berisi hingga 14 elemen. Jika Anda bekerja pada masalah ukuran tetap yang mengharuskan untuk menghitung berkali-kali operasi acak ini, Anda mungkin ingin mencoba kode berikut yang mungkin lebih cepat daripada kode lain karena Math.randomhanya menggunakan sekali (namun melibatkan beberapa operasi penyalinan).

Fungsi berikut tidak akan digunakan, tetapi saya tetap memberikannya; itu mengembalikan indeks dari permutasi yang diberikan (0, 1, 2, …, n-1)sesuai dengan pemetaan satu ke satu yang digunakan dalam pesan ini (yang paling alami ketika menghitung permuasi); itu dimaksudkan untuk bekerja dengan hingga 16 elemen:

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

Kebalikan dari fungsi sebelumnya (diperlukan untuk pertanyaan Anda sendiri) ada di bawah ini; itu dimaksudkan untuk bekerja dengan hingga 16 elemen; mengembalikan permutasi urutan n dari (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;
}

Sekarang, yang Anda inginkan hanyalah:

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

Ini harus bekerja hingga 16 elemen dengan sedikit bias teoritis (meskipun tidak terlihat dari sudut pandang praktis); dapat dilihat sebagai sepenuhnya dapat digunakan untuk 15 elemen; dengan array yang mengandung kurang dari 14 elemen, Anda dapat dengan aman mempertimbangkan sama sekali tidak ada bias.

Thomas Baruchel
sumber
Sangat elegan!
Gershom