This is a JavaScript implementation of Durstenfeld shuffle, which is an optimized version of the Fisher-Yates algorithm:

/* 使用Durstenfeld shuffle算法原地随机化数组 */
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;
    }
}

It selects a random element for each original array element and excludes it from the next draw, just like drawing randomly from a deck of cards.

This clever elimination operation swaps the selected element with the current element, then selects the next random element from the remaining elements, looping backwards for optimal efficiency, ensuring that the random selection is simplified (it can always start from 0), thereby skipping the last element.

The running time of the algorithm is O(n). Note that shuffling is done in-place, so if you don't want to modify the original array, create a copy first using .slice(0).

Edit: Updated to ES6/ECMAScript 2015

The new ES6 allows us to assign two variables at the same time. This is especially convenient when we want to swap the values ​​of two variables, as we can do it in one line of code. Here is a shorter form of the same function that uses this functionality.

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

Like +0

Add Reply 关闭回复

P粉818125805

reply

In fact, the unbiased shuffling algorithm is Fisher-Yates (also known as Knuth) shuffling algorithm.

You can see a great visualization here (original post linked here )

function shuffle(array) {
  let currentIndex = array.length,  randomIndex;

  // While there remain elements to shuffle.
  while (currentIndex != 0) {

    // Pick a remaining element.
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex--;

    // And swap it with the current element.
    [array[currentIndex], array[randomIndex]] = [
      array[randomIndex], array[currentIndex]];
  }

  return array;
}

// Used like so
var arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);

Like +0

Add Reply 关闭回复

P粉818125805

reply