¿Cómo aleatorizar (barajar) una matriz de JavaScript?

1266

Tengo una matriz como esta:

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

¿Cómo puedo aleatorizarlo / barajarlo?

Haga clic en Upvote
fuente
66
Simplemente lanzando esto aquí para que pueda visualizar cuán aleatoria es en realidad una función aleatoria con este visualizador que Mike Bostock hizo: bost.ocks.org/mike/shuffle/compare.html
agosto
55
@Blazemonger jsPref está muerto. ¿Puedes publicar aquí cuál es el más rápido?
eozzy
¿Qué pasa con una línea? La matriz devuelta se baraja. arr1.reduce ((a, v) => a.splice (Math.floor (Math.random () * a.length), 0, v) && a, [])
brunettdan
La solución reducida tiene una complejidad O (n ^ 2). Intenta ejecutarlo en una matriz con un millón de elementos.
riv

Respuestas:

1542

El algoritmo de shuffle imparcial de facto es el Shuffle Fisher-Yates (también conocido como Knuth).

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

Puedes ver una gran visualización aquí (y la publicación original vinculada a esto )

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

Más información sobre el algoritmo utilizado.

CoolAJ86
fuente
13
La respuesta salta el elemento 0 arriba, la condición debe ser i--no --i. Además, la prueba if (i==0)...es superflua, ya que si i == 0el tiempo nunca será entró en bucle. La llamada a Math.floorse puede hacer más rápido usando ...| 0. Se pueden eliminar tempi o tempj y el valor se puede asignar directamente a myArray [i] o j según corresponda.
RobG
23
@prometheus, todos los RNG son pseudoaleatorios a menos que estén conectados a hardware costoso.
Phil H
38
@RobG la implementación anterior es funcionalmente correcta. En el algoritmo Fisher-Yates, el ciclo no está destinado a ejecutarse para el primer elemento de la matriz. Consulte wikipedia donde hay otras implementaciones que también omiten el primer elemento. Consulte también este artículo que explica por qué es importante que el bucle no se ejecute para el primer elemento.
theon
34
@nikola "no es al azar en absoluto" es una calificación un poco fuerte para mí. Yo diría que es lo suficientemente aleatorio a menos que sea un criptógrafo, en cuyo caso probablemente no esté usando Math.Random () en primer lugar.
toon81
20
Ugh, yoda ( 0 !== currentIndex).
ffxsam
746

Aquí hay una implementación de JavaScript del Durstenfeld shuffle , una versión optimizada de 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;
    }
}

Elige un elemento aleatorio para cada elemento de matriz original y lo excluye del siguiente sorteo, como elegir aleatoriamente de una baraja de cartas.

Esta inteligente exclusión intercambia el elemento seleccionado con el actual, luego selecciona el siguiente elemento aleatorio del resto, haciendo un bucle hacia atrás para una eficiencia óptima, asegurando que la selección aleatoria se simplifica (siempre puede comenzar en 0) y, por lo tanto, omite el elemento final.

El tiempo de ejecución del algoritmo es O(n). Tenga en cuenta que la reproducción aleatoria se realiza en el lugar, por lo que si no desea modificar la matriz original, primero haga una copia con ella .slice(0).


EDITAR: Actualización a ES6 / ECMAScript 2015

El nuevo ES6 nos permite asignar dos variables a la vez. Esto es especialmente útil cuando queremos intercambiar los valores de dos variables, ya que podemos hacerlo en una línea de código. Aquí hay una forma más corta de la misma función, utilizando esta función.

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
fuente
22
ps El mismo algoritmo que la respuesta de ChristopheD, pero con explicación e implementación más limpia.
Laurens Holst
12
Las personas atribuyen a la persona equivocada para el algoritmo. No es barajar Fisher-Yates, sino barajar Durstenfeld . El verdadero algoritmo original de Fisher-Yates se ejecuta en n ^ 2 veces, no en n veces
Pacerier
77
No es necesario return arrayya que JavaScript pasa las matrices por referencia cuando se usa como argumentos de función. Supongo que esto es para ahorrar espacio en la pila, pero es una pequeña característica interesante. Al realizar la reproducción aleatoria en la matriz, se barajará la matriz original.
Joel Trauger
55
La implementación en esta respuesta favorece el extremo inferior de la matriz. Descubierto por el camino difícil . Math.random() should not be multiplied with the loop counter + 1, but with array.lengt () `. Ver ¿ Generar números enteros aleatorios en JavaScript en un rango específico? para una explicación muy completa
Marjan Venema
13
@MarjanVenema No estoy seguro si todavía está viendo este espacio, pero esta respuesta es correcta, y el cambio que sugiere en realidad introduce sesgo. Visite blog.codinghorror.com/the-danger-of-naivete para obtener una buena reseña de este error.
user94559
134

¡Advertencia!
Es el uso de este algoritmo no es recomendable , ya que es poco eficiente y fuertemente sesgado ; ver comentarios. Se deja aquí para referencia futura, porque la idea no es tan rara.

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});
muerto
fuente
13
Me gusta esta solución, suficiente para dar un azar básico
Alex K
147
El voto negativo ya que esto no es realmente tan aleatorio. No sé por qué tiene tantos votos a favor. No utilices este método. Se ve bonito, pero no es completamente correcto. Estos son los resultados después de 10,000 iteraciones sobre cuántas veces cada número en su matriz alcanza el índice [0] (también puedo dar los otros resultados): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
radtad
8
Está bien si necesita aleatorizar una matriz relativamente pequeña y no lidiar con cosas criptográficas. Estoy totalmente de acuerdo en que si necesita más aleatoriedad , debe usar una solución más compleja.
muerto el
21
También es el menos eficiente de todos los métodos disponibles .
Blazemonger
12
El problema es que no es determinista, lo que arrojará resultados incorrectos (si 1> 2 y 2> 3, se debe dar que 1> 3, pero esto no garantizará eso. Esto confundirá el tipo y dará como resultado el comentario comentado por @radtad).
MatsLindh
73

Uno podría (o debería) usarlo como un prototipo de Array:

De 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;
}
estafa
fuente
42
Realmente no hay beneficio para esto, IMOHO, excepto posiblemente pisando fuerte en la implementación de otra persona ..
user2864740
2
Si se usa en el prototipo de matriz, debe nombrarse de otra manera que no sea simplemente barajar .
Wolf
57
Uno podría (o debería) evitar extender los prototipos nativos: javascriptweblog.wordpress.com/2011/12/05/…
Wédney Yuri
12
No deberías hacer esto; cada matriz afectada por esto ya no se puede iterar de forma segura utilizando para ... en. No extiendas los prototipos nativos.
18
@TinyGiant En realidad: no use for...inbucles para iterar sobre matrices.
Conor O'Brien el
69

Puede hacerlo fácilmente con el mapa y ordenar:

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. Ponemos cada elemento en la matriz en un objeto y le damos una clave de ordenación aleatoria
  2. Ordenamos usando la clave aleatoria
  3. Desmapeamos para obtener los objetos originales

Puede barajar matrices polimórficas, y el orden es tan aleatorio como Math.random, que es lo suficientemente bueno para la mayoría de los propósitos.

Dado que los elementos se ordenan según claves consistentes que no se regeneran en cada iteración, y cada comparación se extrae de la misma distribución, se cancela cualquier no aleatoriedad en la distribución de Math.random.

Velocidad

La complejidad temporal es O (N log N), igual que la ordenación rápida. La complejidad del espacio es O (N). Esto no es tan eficiente como un shuffle de Fischer Yates pero, en mi opinión, el código es significativamente más corto y más funcional. Si tiene una gran variedad, sin duda debería usar Fischer Yates. Si tiene una pequeña matriz con unos cientos de elementos, puede hacer esto.

superluminario
fuente
1
@superluminary Vaya, tienes razón. Tenga en cuenta que esta respuesta ya utiliza el mismo enfoque.
Bergi
@ Bergi: Ah, sí, tienes razón, aunque creo que mi implementación es un poco más bonita.
superluminary
3
Muy agradable. Esta es la transformación de Schwartz en js.
Mark Grimes
@torazaburo: no es tan eficaz como Fischer Yates, pero es más bonito y el código es más pequeño. El código siempre es una compensación. Si tuviera una gran variedad, usaría Knuth. Si tuviera un par de cientos de artículos, haría esto.
superluminary
1
@BenCarp: de acuerdo, no es la solución más rápida y no querrás usarla en una matriz masiva, pero hay más consideraciones en el código que la velocidad en bruto.
superluminario
64

Use la biblioteca underscore.js. El método _.shuffle()es bueno para este caso. Aquí hay un ejemplo con el 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();
vn_grv
fuente
12
¡Gran respuesta! Gracias. Lo prefiero a las otras respuestas, ya que alienta a las personas a usar bibliotecas en lugar de copiar y pegar funciones potencialmente defectuosas en todas partes.
frabcus
6060
@frabcus: No tiene sentido incluir una biblioteca completa solo para obtener una shufflefunción.
Blender
11
No estoy de acuerdo con @Blender. Hay muchas razones para incluir una biblioteca completa solo para obtener la función que necesita. Uno de ellos es que hay menos riesgo de error cuando lo escribes tú mismo. Si es un problema de rendimiento, entonces no deberías usarlo. Pero el hecho de que pueda ser un problema de rendimiento no significa que lo sea.
Daniel Kaplan
77
@tieTYT: Entonces, ¿por qué necesitas el resto de la biblioteca? El shuffle de Fisher-Yates es trivial de implementar. No necesita una biblioteca para elegir un elemento aleatorio de una matriz (espero), por lo que no hay razón para usar una biblioteca a menos que realmente vaya a usar más de una función de ella.
Licuadora
18
@Blender: di una razón por la cual. 1) Le aseguro que puede introducir un error en cualquier código que escriba, sin importar cuán trivial sea. ¿Por qué arriesgarse? 2) No optimices previamente. 3) El 99% de las veces que necesitas un shuffle algo, tu aplicación no se trata de escribir un shuffle algo. Se trata de algo que necesita algo aleatorio. Aprovechar el trabajo de otros. No piense en los detalles de implementación a menos que tenga que hacerlo.
Daniel Kaplan
50

¡NUEVO!

Algoritmo aleatorio Fisher-Yates más corto y probablemente * más rápido

  1. usa mientras ---
  2. bit a piso (números de hasta 10 dígitos decimales (32 bits))
  3. se eliminaron cierres innecesarios y otras cosas

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
}

tamaño del script (con fy como nombre de la función): 90bytes

MANIFESTACIÓN http://jsfiddle.net/vvpoma8w/

* más rápido probablemente en todos los navegadores, excepto Chrome.

Si tiene alguna pregunta solo pregunte.

EDITAR

si es mas rapido

ACTUACIÓN: http://jsperf.com/fyshuffle

utilizando las funciones más votadas.

EDITAR Hubo un cálculo en exceso (no necesita --c + 1) y nadie se dio cuenta

más corto (4bytes) y más rápido (¡pruébalo!).

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
}

El almacenamiento en caché en otro lugar var rnd=Math.randomy luego el uso rnd()también aumentaría ligeramente el rendimiento en grandes matrices.

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

Versión legible (use la versión original. Esto es más lento, los vars son inútiles, como los cierres & ";", el código en sí también es más corto ... tal vez lea esto Cómo 'minificar' el código Javascript , por cierto no puede comprima el siguiente código en un minifier javascript como el anterior).

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
 }
}
coco
fuente
66
echa un vistazo a la actuación ... 2 veces más rápido en la mayoría de los navegadores ... pero necesita probadores más jsperf ...
Cocco
10
js es un lenguaje que acepta muchos accesos directos y diferentes formas de escribirlo ... mientras que aquí hay muchas funciones leíbles de lectura lenta, me gustaría mostrar cómo se podría hacer de una manera más eficiente, también guardando algunos bytes ... bit a bit y Aquí se subestima realmente la taquigrafía y la web está llena de errores y código lento.
cocco
No es un aumento de Slam Dunk Perf. Cambiando el fyy shuffle prototype, me sale fyconstantemente en la parte inferior en Chrome 37 en OS X 10.9.5 (81% más lento ~ 20k ops en comparación con ~ 100k) y Safari 7.1 es hasta ~ 8% más lento. YMMV, pero no siempre es más rápido. jsperf.com/fyshuffle/3
Spig
verifique las estadísticas nuevamente ... ya escribí que Chrome es más lento porque optimizan las matemáticas, en el resto del piso bit a bit y mientras es más rápido. comprobar IE, Firefox, pero también devices.Would móvil sea también agradable ver la ópera ...
Cocco
1
Esta es una respuesta terrible. SO no es una competencia de oscurecimiento.
Puppy
39

Editar: esta respuesta es incorrecta

Ver comentarios y https://stackoverflow.com/a/18650169/28234 . Se deja aquí como referencia porque la idea no es rara.


Una forma muy simple para arreglos pequeños es simplemente esto:

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

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

Probablemente no sea muy eficiente, pero para arreglos pequeños esto funciona bien. Aquí hay un ejemplo para que pueda ver cuán aleatorio (o no) es, y si se ajusta a su caso de uso o no.

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
fuente
Bonito, pero ¿genera elementos aleatorios completos cada vez?
DDD
No estoy muy seguro si te entendí correctamente. De hecho, este enfoque barajará la matriz de forma aleatoria (aunque sea pseudoaleatoria) cada vez que llame a la matriz de clasificación; no es una clasificación estable, por razones obvias.
Kris Selbekk
44
Por los mismos motivos que se explican en stackoverflow.com/a/18650169/28234 . Es mucho más probable que deje elementos tempranos cerca del inicio de la matriz.
AlexC
77
Este es un excelente y sencillo resumen para cuando necesita mezclar una matriz, pero no le importa demasiado que los resultados sean académicamente demostrables al azar. A veces, esos últimos centímetros a la perfección llevan más tiempo del que vale.
Daniel Griscom
1
Sería maravilloso si esto funcionara, pero no funciona. Debido a la forma en que funciona la búsqueda rápida, es probable que un comparador inconsistente deje los elementos de la matriz cerca de su posición original. Su matriz no será codificada.
superluminario
39

Fiable, eficiente, corto

Algunas soluciones en esta página no son confiables (solo aleatorizan parcialmente la matriz). Otras soluciones son significativamente menos eficientes. Con testShuffleArrayFun(ver más abajo) podemos probar las funciones de combinación aleatoria de la matriz en cuanto a confiabilidad y rendimiento. Las siguientes soluciones son: confiables, eficientes y cortas (usando la sintaxis ES6)

[Las pruebas de comparación se realizaron usando testShuffleArrayFun otras soluciones, en Google Chrome]

Mezclar matriz en su lugar

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

Prueba de confiabilidad y rendimiento

Como puede ver en esta página, se han ofrecido soluciones incorrectas aquí en el pasado. Escribí y he usado la siguiente función para probar cualquier función aleatoria de matriz pura (sin efectos secundarios).

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

Otras soluciones

Otras soluciones solo por diversión.

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]
        )
    }
Ben Carp
fuente
Entonces, ¿dónde está el ES6 (ES2015)? [array[i], array[rand]]=[array[rand], array[i]]? Tal vez puedas describir cómo funciona eso. ¿Por qué eliges iterar hacia abajo?
sheriffderek
@sheriffderek Sí, la función ES6 que estoy usando es la asignación de dos vars a la vez, lo que nos permite intercambiar dos vars en una línea de código.
Ben Carp
Gracias a @sheriffderek que sugirió el algoritmo ascendente. El algoritmo ascendente podría probarse en la inducción.
Ben Carp
23

Agregando a @Laurens Holsts respuesta. Esto es 50% comprimido.

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
fuente
3
Deberíamos alentar a las personas a usar _.shuffle en lugar de pegar código del desbordamiento de pila; y, deberíamos desalentar a las personas de comprimir sus respuestas de desbordamiento de pila. Para eso está jsmin.
David Jones
45
@DavidJones: ¿Por qué incluiría una biblioteca completa de 4 kb solo para mezclar una matriz?
Blender
1
Los insultos de @KingKongFrog tampoco son propicios para el ensamblaje de una comunidad razonable.
Wheaties
2
¿Es eficiente hacerlo var b = en un bucle en lugar de declarar b fuera del bucle y asignarlo b = en un bucle?
Alex K
2
@Brian no hará la diferencia; el izado ocurre cuando se analiza el código fuente. No probablemente involucrado.
user2864740
23

Editar: esta respuesta es incorrecta

Ver https://stackoverflow.com/a/18650169/28234 . Se deja aquí como referencia porque la idea no es 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 es un número aleatorio que puede ser positivo o negativo, por lo que la función de ordenación reordena elementos al azar.

hakiko
fuente
17

Con ES2015 puedes 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();
BrunoLM
fuente
44
Para truncar, debe usar en n >>> 0lugar de ~~n. Los índices de matriz pueden ser superiores a 2³¹-1.
Oriol
1
Una estructura como esta hace una implementación tan limpia +1
lukejacksonn
14

Encontré esta variante colgando en las respuestas "eliminado por el autor" en un duplicado de esta pregunta. A diferencia de algunas de las otras respuestas que ya tienen muchos votos positivos, esto es:

  1. En realidad al azar
  2. No en el lugar (de ahí el shufflednombre en lugar de shuffle)
  3. No está presente aquí con múltiples variantes.

Aquí hay un jsfiddle que lo muestra en uso .

Array.prototype.shuffled = function() {
  return this.map(function(n){ return [Math.random(), n] })
             .sort().map(function(n){ return n[1] });
}
Daniel Martin
fuente
(Sospecho que se eliminó, ya que es una forma muy ineficiente de aleatorizar la matriz, especialmente para matrices más grandes ... mientras que la respuesta aceptada y varios otros clones de esa respuesta se aleatorizan en el lugar).
WiredPrairie
1
Sí, pero dado que la conocida respuesta incorrecta todavía tiene muchos votos, al menos debería mencionarse una solución ineficiente pero correcta.
Daniel Martin
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });- no da un orden aleatorio, y si lo usa puede terminar avergonzado: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
Daniel Martin
3
Debe usarlo .sort(function(a,b){ return a[0] - b[0]; })si desea que el ordenamiento compare valores numéricamente. El .sort()comparador predeterminado es lexicográfico, lo que significa que se considerará 10menor que 2ya que 1es menor que 2.
4castle
@ 4castle Bien, actualicé el código, pero lo revertiré: la distinción entre el orden lexicográfico y el orden numérico no importa para los números en el rango que Math.random()produce. (es decir, el orden lexicográfico es el mismo que el orden numérico cuando se trata de números del 0 (inclusive) al 1 (exclusivo))
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
fuente
Obviamente, esto no es tan óptimo como el algoritmo de Fisher-Yates, pero ¿funcionaría para entrevistas técnicas?
davidatthepark
@Andrea El código se rompió debido al hecho de que la longitud de la matriz se cambia dentro del ciclo for. Con la última edición, esto se corrige.
Charlie Wallace
12
arr1.sort(() => Math.random() - 0.5);
Sam Doidge
fuente
1
¿Por qué menos 0.5? ¿Qué significa ese número?
Sartheris Martillo de tormenta
1
@SartherisStormhammer porque estamos usando una función CompareFunction para la clasificación, y si eso devuelve un número mayor que 0, los elementos que se comparan se ordenarán solo en dirección. -0.5 en Math.random () nos dará un número negativo ~ 50% del tiempo, lo que nos da el orden inverso.
Sam Doidge
Solución directa y más simple. Gracias
deanwilliammills
9

Puedes hacerlo fácilmente con:

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

Consulte las matrices de ordenación de JavaScript

Tính Ngô Quang
fuente
Este algoritmo ha demostrado ser defectuoso durante mucho tiempo.
Por favor, demuéstramelo. Me basé en w3schools
Tính Ngô Quang
44
Puede leer el hilo en css-tricks.com/snippets/javascript/shuffle-array , o en news.ycombinator.com/item?id=2728914 . W3schools siempre ha sido, y sigue siendo, una fuente horrible de información.
Para una buena discusión sobre por qué este no es un buen enfoque, consulte stackoverflow.com/questions/962802/…
Charlie Wallace
8

Una solución 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));
};
Julian
fuente
8

Fisher-Yates baraja en javascript. Estoy publicando esto aquí porque el uso de dos funciones de utilidad (swap y randInt) aclara el algoritmo en comparación con las otras respuestas aquí.

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

En primer lugar, eche un vistazo aquí para ver una excelente comparación visual de los diferentes métodos de clasificación en JavaScript.

En segundo lugar, si echas un vistazo rápido al enlace de arriba, verás que el random ordertipo parece funcionar relativamente bien en comparación con los otros métodos, a la vez que es extremadamente fácil y rápido de implementar como se muestra a continuación:

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

Editar : como señaló @gregers, la función de comparación se llama con valores en lugar de índices, por lo que debe usarla indexOf. Tenga en cuenta que este cambio hace que el código sea menos adecuado para matrices más grandes, ya que se indexOfejecuta en tiempo O (n).

Milo Wielondek
fuente
Array.prototype.sortpasa en dos valores como ay b, no el índice. Entonces este código no funciona.
gregers
@gregers tienes razón, he editado la respuesta. Gracias.
Milo Wielondek
1
Esto no es muy al azar. Dependiendo de la implementación de sort, un elemento en el índice de matriz más bajo puede requerir más comparaciones para llegar al índice más alto que el elemento al lado del índice más alto. Esto significa que es menos probable que el elemento en el índice más bajo llegue al índice más alto.
1 'O 1 -
7

una función aleatoria que no cambia la matriz fuente

Actualización : Aquí estoy sugiriendo un algoritmo relativamente simple (no desde una perspectiva de complejidad ) y corto que funcionará bien con matrices de pequeño tamaño, pero definitivamente va a costar mucho más que el algoritmo clásico de Durstenfeld cuando se trata de matrices enormes. Puede encontrar el Durstenfeld en una de las principales respuestas a esta pregunta.

Respuesta original:

Si no desea que su función aleatoria mute la matriz fuente , puede copiarla en una variable local y luego hacer el resto con una simple lógica aleatoria .

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

Lógica aleatoria : seleccione un índice aleatorio, luego agregue el elemento correspondiente a la matriz de resultados y elimínelo de la copia de la matriz de origen . Repita esta acción hasta que la matriz fuente se vacíe .

Y si realmente lo quieres corto, aquí está lo lejos que podría llegar:

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
fuente
Este es esencialmente el algoritmo original de Fisher-Yates, splicesiendo una forma terriblemente ineficiente de hacer lo que llamaron "ponchar". Si no desea mutar la matriz original, simplemente cópiela y luego baraje esa copia en su lugar utilizando la variante de Durstenfeld mucho más eficiente.
@torazaburo, gracias por tus comentarios. He actualizado mi respuesta, para dejar en claro que prefiero ofrecer una solución atractiva, en lugar de una súper escala
Evgenia Manolova el
También podemos usar el splicemétodo para crear una copia de este modo: source = array.slice();.
Taiga
6

Aquí está el más fácil ,

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

por ejemplo, puedes consultarlo aquí

Aljohn Yamaro
fuente
5

Otra implementación más de Fisher-Yates, usando el modo estricto:

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;
}
Rafael C
fuente
¿Qué valor aporta la estricta adición de uso sobre la respuesta aceptada?
shortstuffsushi
Para obtener más información sobre el modo estricto y cómo influye en el rendimiento, puede leerlo aquí: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
Raphael C
Hmm, ¿podría señalar algo específico del documento referenciado? Nada allí parece hacer referencia a "mejorar el rendimiento", aparte de un vago comentario en la parte superior sobre la posibilidad de dificultar la optimización del motor js. En este caso, no me queda claro qué uso estricto mejoraría.
shortstuffsushi
El modo estricto ha existido durante bastante tiempo, y hay suficientes lecturas para que cualquiera pueda opinar por sí mismo si siempre debe usarlo o no y por qué. Jslint, por ejemplo, deja en claro que siempre debe usar el modo estricto. Douglas Crockford ha escrito una gran cantidad de artículos y algunos excelentes videos sobre por qué es importante usar siempre el modo estricto no solo como una buena práctica, sino también cómo los motores de js del navegador, como V8, lo interpretan de manera diferente. Te recomiendo encarecidamente que lo busques en Google y hagas tu propia opinión al respecto.
Raphael C
Aquí hay un viejo hilo sobre perfs en modo estricto, un poco viejo pero relevante: stackoverflow.com/questions/3145966/…
Raphael C
5

Todas las otras respuestas se basan en Math.random (), que es rápido pero no adecuado para la aleatorización de nivel criptográfico.

El código siguiente está utilizando el bien conocido Fisher-Yatesalgoritmo mientras que la utilización Web Cryptography APIde nivel criptográfico de asignación al azar .

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
fuente
4

Solución moderna en línea corta que utiliza las funciones de ES6:

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

(con fines educativos)

icl7126
fuente
4

Una modificación simple de la respuesta de CoolAJ86 que no modifica la 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;
};
abumalick
fuente
4

Aunque ya hay una serie de implementaciones recomendadas, creo que podemos hacerlo más corto y fácil usando forEach loop, por lo que no debemos preocuparnos por calcular la longitud de la matriz y también podemos evitar con seguridad el uso de una variable temporal.

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
fuente
4

Solo para tener un dedo en el pastel. Aquí presento una implementación recursiva de Fisher Yates shuffle (creo). Da aleatoriedad uniforme.

Nota: El ~~(operador de doble tilde) se comporta de hecho como Math.floor()para números reales positivos. Solo un atajo es.

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

Editar: El código anterior es O (n ^ 2) debido al empleo de .splice()pero podemos eliminar el empalme y la combinación aleatoria en O (n) mediante el truco de intercambio.

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

El problema es que JS no puede cooperar con grandes recursiones. En este caso particular, el tamaño de su matriz está limitado con 3000 ~ 7000, dependiendo del motor de su navegador y algunos hechos desconocidos.

Redu
fuente
3

Aleatorizar matriz

 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
fuente
No debería haber un -1for n ya que <no lo <=
usaste
3

la arrayShufflefunción más corta

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
fuente
Aparentemente estás haciendo Sattolo's en lugar de Fisher-Yates (Knuth, imparcial).
Arthur2e5
3

Desde un punto de vista teórico, la forma más elegante de hacerlo, en mi humilde opinión, es obtener un único número aleatorio entre 0 y n! -1 y calcular un mapeo uno a uno de {0, 1, …, n!-1}todas las permutaciones de(0, 1, 2, …, n-1) . Siempre que pueda usar un generador (pseudo-) aleatorio lo suficientemente confiable como para obtener dicho número sin ningún sesgo significativo, tendrá suficiente información para lograr lo que desea sin necesidad de varios otros números aleatorios.

Al calcular con números flotantes de precisión doble IEEE754, puede esperar que su generador aleatorio proporcione aproximadamente 15 decimales. Como tiene 15! = 1,307,674,368,000 (con 13 dígitos), puede usar las siguientes funciones con matrices que contienen hasta 15 elementos y asumir que no habrá sesgo significativo con matrices que contengan hasta 14 elementos. Si trabaja en un problema de tamaño fijo que requiere calcular muchas veces esta operación aleatoria, puede probar el siguiente código, que puede ser más rápido que otros códigos ya que Math.randomsolo se usa una vez (sin embargo, implica varias operaciones de copia).

La siguiente función no se utilizará, pero la doy de todos modos; devuelve el índice de una permutación dada de (0, 1, 2, …, n-1)acuerdo con el mapeo uno a uno utilizado en este mensaje (el más natural al enumerar permuciones); Está diseñado para trabajar con hasta 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);
}

El recíproco de la función anterior (requerido para su propia pregunta) está abajo; está diseñado para trabajar con hasta 16 elementos; devuelve la permutación de orden 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;
}

Ahora, lo que quieres simplemente es:

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

Debería funcionar para hasta 16 elementos con un pequeño sesgo teórico (aunque imperceptible desde un punto de vista práctico); se puede ver como totalmente utilizable para 15 elementos; con matrices que contienen menos de 14 elementos, puede considerar con seguridad que no habrá absolutamente ningún sesgo.

Thomas Baruchel
fuente
Definitivamente elegante!
Gershom