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

/* 使用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 selecting randomly from a deck of cards.

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

The running time of the algorithm is O(n). It should be noted that this shuffling is performed in place, so if you do not want to modify the original array, please use the .slice(0) method to make a copy first.

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. This is a shorter form of the same function that uses this feature.

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粉877719694

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粉877719694

reply