Eu tenho uma matriz como esta:

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

Como posso aleatorizar / embaralhar?

O algoritmo shuffle imparcial de fato é o Shuffle de Fisher-Yates (também conhecido como Knuth).

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

Você pode ver uma ótima visualização aqui (e a postagem original vinculada a isso )

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

Mais algumas informações sobre o algoritmo usado.

Aqui está uma implementação em JavaScript do Durstenfeld shuffle , uma versão otimizada do Fisher-Yates:

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

Ele escolhe um elemento aleatório para cada elemento original da matriz e o exclui do próximo sorteio, como escolher aleatoriamente um baralho de cartas.

Essa exclusão inteligente troca o elemento selecionado pelo atual e, em seguida, escolhe o próximo elemento aleatório do restante, fazendo um loop para trás para obter uma eficiência ideal, garantindo que a seleção aleatória seja simplificada (sempre pode começar em 0) e, assim, pulando o elemento final.

O tempo de execução do algoritmo é O(n). Observe que o shuffle é feito no local, portanto, se você não quiser modificar a matriz original, primeiro faça uma cópia dela .slice(0).

EDIT: Atualizando para ES6 / ECMAScript 2015

O novo ES6 nos permite atribuir duas variáveis ​​ao mesmo tempo. Isso é especialmente útil quando queremos trocar os valores de duas variáveis, pois podemos fazer isso em uma linha de código. Aqui está uma forma mais curta da mesma função, usando esse recurso.

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

Atenção!
O uso desse algoritmo não é recomendado , pois é ineficiente e fortemente enviesado ; Ver comentários. Ele está sendo deixado aqui para referência futura, porque a idéia não é tão rara.

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

Pode-se (ou deveria) usá-lo como um protoype da Matriz:

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

Você pode fazer isso facilmente com o mapa e classificar:

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. Colocamos cada elemento na matriz em um objeto e atribuímos a ele uma chave de classificação aleatória
2. Classificamos usando a chave aleatória
3. Desmapeamos para obter os objetos originais

Você pode embaralhar matrizes polimórficas e a classificação é tão aleatória quanto Math.random, o que é bom o suficiente para a maioria dos propósitos.

Como os elementos são classificados com chaves consistentes que não são regeneradas a cada iteração e cada comparação é extraída da mesma distribuição, qualquer não aleatoriedade na distribuição do Math.random é cancelada.

Rapidez

A complexidade do tempo é O (N log N), o mesmo que a classificação rápida. A complexidade do espaço é O (N). Isso não é tão eficiente quanto um embaralhamento Fischer Yates, mas, na minha opinião, o código é significativamente mais curto e mais funcional. Se você possui uma grande variedade, certamente deve usar o Fischer Yates. Se você tiver uma pequena matriz com algumas centenas de itens, faça isso.

Use a biblioteca underscore.js. O método _.shuffle()é bom para este caso. Aqui está um exemplo com o método:

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

NOVO!

Algoritmo de embaralhamento Fisher-Yates mais curto e provavelmente mais rápido

1. usa enquanto ---
2. bit a bit para andar (números de até 10 dígitos decimais (32 bits))
3. removidos fechamentos desnecessários e outras coisas

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
}

tamanho do script (com fy como nome da função): 90bytes

DEMO http://jsfiddle.net/vvpoma8w/

* mais rápido, provavelmente em todos os navegadores, exceto no Chrome.

Se você tiver alguma dúvida, basta perguntar.

EDITAR

sim é mais rapido

DESEMPENHO: http://jsperf.com/fyshuffle

usando as principais funções votadas.

EDITAR Houve um cálculo em excesso (não precisa --c + 1) e ninguém notou

mais curto (4 bytes) e mais rápido (teste!).

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
}

Armazenar em cache em outro lugar var rnd=Math.randome depois usá-lo rnd()também aumentaria um pouco o desempenho em grandes matrizes.

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

Versão legível (use a versão original. Isso é mais lento, vars são inúteis, como os fechamentos & ";", o próprio código também é mais curto ... talvez leia isto Como 'minificar' o código Javascript , mas você não é capaz de comprima o código a seguir em minificadores de javascript como o acima.)

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

Editar: esta resposta está incorreta

Consulte os comentários e https://stackoverflow.com/a/18650169/28234 . Está sendo deixado aqui para referência, porque a idéia não é rara.

Uma maneira muito simples para pequenas matrizes é simplesmente esta:

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

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

Provavelmente não é muito eficiente, mas para pequenas matrizes isso funciona muito bem. Aqui está um exemplo para que você possa ver como é aleatório (ou não) e se ele se encaixa no seu caso de uso ou não.

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>

Confiável, Eficiente, Curto

Algumas soluções nesta página não são confiáveis ​​(elas apenas aleatoriamente parcialmente a matriz). Outras soluções são significativamente menos eficientes. Com testShuffleArrayFun(veja abaixo), podemos testar as funções de embaralhamento da matriz para obter confiabilidade e desempenho. As seguintes soluções são: confiáveis, eficientes e curtas (usando a sintaxe ES6)

[Testes de comparação foram feitos com testShuffleArrayFunoutras soluções, no 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 Puro, Iterativo

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

Teste de confiabilidade e desempenho

Como você pode ver nesta página, houve soluções incorretas oferecidas aqui no passado. Eu escrevi e usei a seguinte função para testar qualquer função aleatória pura de matriz (sem efeitos colaterais).

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

Outras soluções

Outras soluções apenas por diversão.

ES6 Puro, Recursivo

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

Adicionando à resposta @Laurens Holsts. Isso é 50% compactado.

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

Editar: esta resposta está incorreta

Consulte https://stackoverflow.com/a/18650169/28234 . Está sendo deixado aqui para referência, porque a idéia não é rara.

//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 é um número aleatório que pode ser positivo ou negativo; portanto, a função de classificação reordena os elementos aleatoriamente.

Com o ES2015, você pode usar este:

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

Uso:

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

Encontrei essa variante nas respostas "excluídas pelo autor" em uma duplicata desta pergunta. Ao contrário de algumas das outras respostas que já têm muitos votos positivos, isso é:

1. Realmente aleatório
2. Não está no local (daí o shufflednome shuffle)
3. Ainda não está presente aqui com várias variantes

Aqui está um jsfiddle mostrando-o em uso .

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

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

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

Você pode fazer isso facilmente com:

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

Consulte em JavaScript Sorting Arrays

Uma solução recursiva:

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

Embaralhamento de Fisher-Yates em javascript. Estou postando isso aqui porque o uso de duas funções utilitárias (swap e randInt) esclarece o algoritmo comparado às outras respostas aqui.

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

Antes de tudo, dê uma olhada aqui para uma ótima comparação visual de diferentes métodos de classificação em javascript.

Em segundo lugar, se você der uma olhada rápida no link acima, verá que o random ordertipo parece ter um desempenho relativamente bom em comparação com outros métodos, além de ser extremamente fácil e rápido de implementar, como mostrado abaixo:

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

Edit : como apontado por @gregers, a função de comparação é chamada com valores em vez de índices, e é por isso que você precisa usar indexOf. Observe que essa alteração torna o código menos adequado para matrizes maiores à medida que indexOfé executado no tempo O (n).

uma função aleatória que não altera a matriz de origem

Atualização : aqui estou sugerindo um algoritmo relativamente simples (não da perspectiva da complexidade ) e curto que funcionará bem com matrizes de tamanho pequeno, mas definitivamente vai custar muito mais do que o algoritmo clássico de Durstenfeld quando você lida com matrizes enormes. Você pode encontrar o Durstenfeld em uma das principais respostas a esta pergunta.

Resposta original:

Se você não deseja que a função de reprodução aleatória mude a matriz de origem , copie-a para uma variável local e faça o resto com uma lógica de reprodução aleatória simples .

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

Baralhar lógica : escolha um índice aleatório e adicione o elemento correspondente à matriz de resultados e exclua-o da cópia da matriz de origem . Repita esta ação até que a matriz de origem fique vazia .

E se você realmente quer que ele seja curto, aqui está o quão longe eu poderia chegar:

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

Aqui está o mais fácil ,

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

Para mais exemplos, você pode conferir aqui

mais uma implementação do Fisher-Yates, usando o modo estrito:

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

Todas as outras respostas são baseadas em Math.random (), que é rápido, mas não é adequado para a randomização no nível criptográfico.

O código abaixo está usando o conhecido Fisher-Yatesalgoritmo enquanto utiliza Web Cryptography APIpara o nível criptográfico de randomização .

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

Solução moderna em linha curta usando os recursos do ES6:

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

(para fins educacionais)

Uma modificação simples da resposta de CoolAJ86 que não modifica a matriz original:

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

Embora já existam várias implementações recomendadas, mas acho que podemos torná-lo mais curto e fácil usando o loop forEach, portanto, não precisamos nos preocupar em calcular o comprimento da matriz e também podemos evitar o uso seguro de uma variável temporária.

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)

Só para ter um dedo na torta. Aqui apresento uma implementação recursiva do embaralhamento de Fisher Yates (eu acho). Dá aleatoriedade uniforme.

Nota: O ~~(operador double til) na verdade se comporta como Math.floor()para números reais positivos. É só um atalho.

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

Edit: O código acima é O (n ^ 2) devido ao emprego de, .splice()mas podemos eliminar emendas e embaralhamento em O (n) pelo truque de 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");

O problema é que o JS não pode cooperar com grandes recursões. Nesse caso em particular, o tamanho da sua matriz é limitado a 3000 ~ 7000, dependendo do mecanismo do navegador e de alguns fatos desconhecidos.

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

a arrayShufflefunção mais curta

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

Do ponto de vista teórico, a maneira mais elegante de fazê-lo, na minha humilde opinião, é obter um único número aleatório entre 0 e n! -1 e calcular um mapeamento de um para um de {0, 1, …, n!-1}todas as permutações de(0, 1, 2, …, n-1) . Contanto que você possa usar um gerador (pseudo-) aleatório confiável o suficiente para obter um número sem viés significativo, você terá informações suficientes para alcançar o que deseja sem precisar de vários outros números aleatórios.

Ao calcular com números flutuantes de precisão dupla IEEE754, você pode esperar que seu gerador aleatório forneça cerca de 15 casas decimais. Como você possui 15! = 1.307.674.368.000 (com 13 dígitos), é possível usar as seguintes funções com matrizes que contêm até 15 elementos e assumir que não haverá viés significativo com matrizes que contêm até 14 elementos. Se você trabalha com um problema de tamanho fixo que exige calcular muitas vezes essa operação de reprodução aleatória, tente o código a seguir, que pode ser mais rápido que outros códigos, pois ele usaMath.random apenas uma vez (no entanto, envolve várias operações de cópia).

A seguinte função não será usada, mas eu a dou de qualquer maneira; retorna o índice de uma dada permutação de (0, 1, 2, …, n-1)acordo com o mapeamento de um para um usado nesta mensagem (o mais natural ao enumerar as permutas); destina-se a trabalhar com até 16 elementos:

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

O recíproco da função anterior (necessário para sua própria pergunta) está abaixo; destina-se a trabalhar com até 16 elementos; retorna a permutação da ordem n de (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;
}

Agora, o que você deseja é apenas:

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

Deverá funcionar com até 16 elementos com um pequeno viés teórico (embora imperceptível do ponto de vista prático); pode ser visto como totalmente utilizável por 15 elementos; com matrizes contendo menos de 14 elementos, você pode considerar com segurança que não haverá absolutamente nenhum viés.