In-depth analysis of javascript random shuffling algorithm_javascript skills

Shuffling algorithm is a common random problem that we often encounter when playing games and random sorting. It can be abstracted like this: get a random sequence array of all natural numbers within M.

Searching "Shuffling Algorithm" on Baidu, the first result is "Baidu Library-Shuffling Algorithm". After scanning the contents, many contents can easily mislead others into going astray, including the use of linked lists instead of arrays in the end. It is also only a limited optimization (linked lists also introduce a loss of read efficiency).

The first method in this article can be simply described as: randomly draw cards and put them in another group; draw them again. If you draw an empty card, repeat the draw.
"If you draw an empty card, draw it again." This will lead to an increasing chance of drawing an empty card later, which is obviously unreasonable.
It can be optimized in one step: after the cards are removed, the original cards will be reduced. (Instead of leaving an empty card)
The code is as follows:

Copy the codeThe code is as follows:

function shuffle_pick_1(m) //Shuffle//Card drawing method
{
//Generate m cards
var arr = new Array(m);
for (var i=0 ; i arr[i] = i;
}

//Draw one card each time and put it in another pile. Because you have to extract elements from the array and pull all subsequent elements forward by one, it is very time-consuming.
var arr2 = new Array();
for (var i=m; i>0; i--) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}

This is also obviously problematic, because if the array is very large, deleting an element in the middle will cause the subsequent queue to move forward, which is a very time-consuming action.
Recall "Why do we delete that element?" The purpose is not to produce empty cards.
In addition to deleting that element, are there any other ways for us to remove empty cards?
----Yes, we just put the last undrawn card in the drawn position.
So, we can optimize this idea like this:

Copy code The code is as follows:

function shuffle_pick(m) //shuffle//pump Card optimization card
{
// Generate m cards
var arr = new Array(m);
for (var i=0; i arr [i] = i;
}

//Draw one card each time and put it in another pile. Place the last undrawn card on the empty seat.
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2 .push(arr[rnd]);
arr[rnd] = arr[--i];
}
return arr2;
}

Except for drawing cards As for the idea, we can also use the idea of ​​changing cards.
"Baidu Wenku - Shuffling Algorithm" mentions an idea of ​​​​changing cards: "Randomly exchange two positions for a total of n times. The larger n is, the closer it is to randomness."
This approach is wrong. Even if n is very large (for example, 10 cards, 10 swaps), there is still a high possibility that "some cards have not changed positions at all".
Following this idea, just make a small adjustment: change the position of the i-th card with any other card, and then finish the round.
The code is as follows:

Copy code The code is as follows:

function shuffle_swap(m) //shuffle//swap Card method
{
// Generate m cards
var arr = new Array(m);
for (var i=0; i arr[i ] = i;
}

//Swap the i-th card with any card after one round
for (var i=0; i var rnd = Math.floor( Math.random()*(i 1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}

In addition to the idea of ​​drawing and exchanging cards, we can also use the idea of ​​inserting cards: there is one card first, the second card has two positions that can be randomly inserted (before or after the first card), and the third There are three positions for a card to be randomly inserted (at the back, or in the first place, or in the second place), and so on
The code is as follows:

Copy code The code is as follows:

function shuffle_insert_1(m) //shuffle//insert Card method
{
//Generate the largest card each time and insert it in front of a random card. Because you need to insert elements into the array and push all subsequent elements back one position, it is very time-consuming.
var arr = [0];
for (var i=1; i arr.splice(Math.floor(Math.random()*(i 1)), 0,i);
}
return arr;
}

The above code will also have some problems: as the number of cards increases, it becomes more and more difficult to insert cards, because inserting cards will cause many subsequent cards to be pushed back.
Of course, we can also optimize it appropriately: there are n-1 cards first, the n-th card is placed at the end, and then it swaps positions with any card.
The code is as follows:

Copy code The code is as follows:

function shuffle_insert(m) //shuffle//insert The optimized version of the card method can be proved by mathematical induction that this kind of shuffling is uniform.
{
//Generate the highest card each time and swap places with a random card
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i var rnd = Math.floor(Math.random()*(i 1));
arr[i] = arr[rnd] ;
arr[rnd] = i;
}
return arr;
}

Okay, the whole code is as follows. Interested students can try it on their own machines to see their respective execution efficiency and whether the final result is theoretically random.

Copy code The code is as follows:

< title>JK：javascript shuffling algorithm