Πώς να τυχαιοποιήσετε (ανακατέψετε) έναν πίνακα JavaScript;

Ο ντε φάκτο αλγόριθμος αμερόληπτης αναδιάταξης είναι ο αλγόριθμος Fisher-Yates (γνωστός και ως Knuth) Shuffle.

Βλέπε https://github.com/coolaj86/knuth-shuffle

Μπορείτε να δείτε μια [εξαιρετική οπτικοποίηση εδώ][0] (και την αρχική δημοσίευση [που συνδέεται με αυτό][1])

Εδώ είναι μια JavaScript υλοποίηση του Durstenfeld shuffle, μια βελτιστοποιημένη για υπολογιστή έκδοση του Fisher-Yates:

/**
 * Randomize array element order in-place.
 * Using Durstenfeld shuffle algorithm.
 */
function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Ο αλγόριθμος Fisher-Yates λειτουργεί επιλέγοντας ένα τυχαίο στοιχείο για κάθε αρχικό στοιχείο του πίνακα και στη συνέχεια αποκλείοντάς το από την επόμενη κλήρωση. Ακριβώς όπως η τυχαία επιλογή από μια τράπουλα.

Αυτός ο αποκλεισμός γίνεται με έναν έξυπνο τρόπο (που εφευρέθηκε από τον Durstenfeld για χρήση από υπολογιστές), ανταλλάσσοντας το επιλεγμένο στοιχείο με το τρέχον στοιχείο, και στη συνέχεια επιλέγοντας το επόμενο τυχαίο στοιχείο από το υπόλοιπο. Για βέλτιστη αποδοτικότητα, ο βρόχος εκτελείται προς τα πίσω, έτσι ώστε η τυχαία επιλογή να απλοποιείται (μπορεί πάντα να ξεκινάει από το 0), και παραλείπει το τελευταίο στοιχείο επειδή δεν υπάρχουν άλλες επιλογές πλέον.

Ο χρόνος εκτέλεσης αυτού του αλγορίθμου είναι O(n). Σημειώστε ότι το ανακάτεμα γίνεται in-place. Έτσι, αν δεν θέλετε να τροποποιήσετε τον αρχικό πίνακα, κάντε πρώτα ένα αντίγραφο του με την .slice(0).

Ενημέρωση σε ES6 / ECMAScript 2015

Το νέο ES6 μας επιτρέπει να αναθέτουμε δύο μεταβλητές ταυτόχρονα. Αυτό είναι ιδιαίτερα βολικό όταν θέλουμε να ανταλλάξουμε τις τιμές δύο μεταβλητών, καθώς μπορούμε να το κάνουμε με μία γραμμή κώδικα. Ακολουθεί μια συντομότερη μορφή της ίδιας συνάρτησης, χρησιμοποιώντας αυτή τη δυνατότητα.

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

Κάποιος θα μπορούσε (ή θα έπρεπε) να το χρησιμοποιήσει ως πρωτότυπο από το Array:

Από τον 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;
}