The shuffling algorithm is a common random problem that we encounter when playing games and randomly sorting. It can be abstracted like this: get a random order array of all natural numbers within M.
Searching for "reshuffle algorithm" on Baidu, the first result was "Baidu Library - reshuffle algorithm". After scanning the contents, many of the contents are easy to mislead others astray, including using linked lists to replace arrays in the end, which is just a limited optimization (link lists also introduce the 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, draw them repeatedly when you draw the empty cards.
"Draw the cards after drawing them again" will lead to the increasing chance of drawing the cards later, which is obviously unreasonable.
One step can be optimized: after the cards are drawn, the original cards become fewer. (rather than leaving empty cards)
The code is as follows:
The code copy is as follows:
function shuffle_pick_1(m) //Shush//Card drawing method
{
//Generate m cards
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//Draw one card at a time and place it in another pile. Because you need to extract elements from the array and pull all the subsequent elements forward one by one, it is 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 large, deleting a certain element in the middle will cause the queue to take a step forward, which is a very time-consuming action.
Recall the purpose of "Why do we delete that element?" is to avoid empty cards.
In addition to deleting that element, do we have other ways to remove empty cards?
----Yes, we just need to put the last undrawn card in the draw position.
So, we can optimize this idea as follows:
The code copy is as follows:
function shuffle_pick(m) //Shut//Card drawing method to optimize card
{
//Generate m cards
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//Draw one card at a time and place it in another pile. Put the last undrawn card on the open 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;
}
In addition to the idea of drawing cards, we can also use the idea of changing cards.
"Baidu Wenku-Shut Algorithm" mentions a card change idea: "Switch two positions randomly, and exchange them n times in total. The larger the n, the closer it is to random."
This approach is wrong. Even if n is very large (for example, 10 cards, 10 switches), there is still a high possibility that "some cards do not change positions at all."
Follow this idea and make a little adjustment: change the i-th card with any card, and just change it for one round.
The code is as follows:
The code copy is as follows:
function shuffle_swap(m) //Shush//Card change method
{
//Generate m cards
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//The i-th card is used to change the seats and you can change it for one round
for (var i=0; i<m; 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 changing cards, we can also use the idea of inserting cards: first there is one card, the second card has two positions to be inserted randomly (before or behind the first card), the third card has three positions to be inserted randomly (placed behind, or inserted in the first position, or inserted in the second position), and so on
The code is as follows:
The code copy is as follows:
function shuffle_insert_1(m) //Shunt//Card insertion method
{
//Each time, the largest card is generated and inserted in front of a random card. Because you need to insert elements into the array and squeeze all the subsequent elements back one by one, it is time-consuming.
var arr = [0];
for (var i=1; i<m; 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 lead to many of the cards that follow one step back.
Of course, we can also optimize appropriately: first there is n-1 card, the n-th card is placed at the end, and then exchange positions with any card.
The code is as follows:
The code copy is as follows:
function shuffle_insert(m) //Shush//Optimized version of the card insertion method can be proved by mathematical induction that this shuffle is uniform.
{
//Each time generates the largest card and exchanges positions with a random card
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1));
arr[i] = arr[rnd];
arr[rnd] = i;
}
return arr;
}
OK, all the codes are as follows. Interested students can try them on their own machine to see if their respective execution efficiency and whether the final result is theoretically random.
The code copy is as follows:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<title>JK: javascript shuffling algorithm</title>
</head>
<body>
<script type="text/javascript">
function shuffle_pick_1(m) //Shush//Card drawing method
{
//Generate m cards
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//Draw one card at a time and place it in another pile. Because you need to extract elements from the array and pull all the subsequent elements forward one by one, it is 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;
}
function shuffle_pick(m) //Shut//Card drawing method to optimize card
{
//Generate m cards
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//Draw one card at a time and place it in another pile. Put the last undrawn card on the open 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;
}
function shuffle_swap(m) //Shush//Card change method
{
//Generate m cards
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//The i-th card is used to change the seats and you can change it for one round
for (var i=0; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}
function shuffle_insert_1(m) //Shunt//Card insertion method
{
//Each time, the largest card is generated and inserted in front of a random card. Because you need to insert elements into the array and squeeze all the subsequent elements back one by one, it is time-consuming.
var arr = [0];
for (var i=1; i<m; i++) {
arr.splice(Math.floor(Math.random()*(i+1)),0,i);
}
return arr;
}
function shuffle_insert(m) //Shush//Optimized version of the card insertion method can be proved by mathematical induction that this shuffle is uniform.
{
//Each time generates the largest card and exchanges positions with a random card
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1));
arr[i] = arr[rnd];
arr[rnd] = i;
}
return arr;
}
//alert(shuffle_pick(10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
funcNames = ["Draw Card", "Draw Card Optimization", "Card Change", "Card Insert", "Card Insert Optimization"]
m = 10000,
times=[];
for(var i = 0; i < funcs.length; i++){
var d0= new Date();
funcs[i](m);
funcNames[i] = (new Date() - d0) + '/t' + funcNames[i];
}
alert(funcNames.join('/n'));
</script>
</body>
</html>