“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”

In understanding the P/NP problem, I have the illusion that I have hit the ceiling of human cognition. !

Our current world is still based on P ≠ NP, so there’s good reason to believe that if we shuffle our cards around enough, luck may come our way. Life is like League of Legends, a game of luck.

This article is: how to shuffle the card shuffle algorithm chaos enough!

From bronze to king, interview and actual combat are used! Like my favorite ✨

Idle words less Syria, direct Aoli to!!

Bronze shuffle 🤬

Title: give you a brand new deck of cards (54), how do you“Shuffled”It??

We bronze players are usually grumpy!

Is not shuffling! Smart bronze players, start by abstracting the problem into an algorithmic model!

The question becomes:

Known: an array nums = [1, 2, 3, 4, 5,…, 51,52,53,54], solving: a new array radomNums out-of-order. (Couldn’t be nicer)

Then use [Violence extraction]

Generate a random integer between 1 and 54 and place it in the new array. Then generate a random integer. If it does not duplicate the previous one, place it in the new array

Until all the numbers in the array are extracted and put into the new array, the final solution!

Code implementation:

// generate nums: let nums=[] for(let I =1; i<=54; I ++){nums.push(I)}  let count = 0 const shuffle = function(nums) { let radomNums = [] while (radomNums.length < nums.length) { count++; Rand = randOne() if(radomnums.includes (rand)){rand = randOne()}else{ RadomNums. Push (rand)}} return radomNums} const randOne= function() { return Math.floor(Math.random() * 54) + 1; } console.log(shuffle(nums)) console.log(count) // (54) [22, 48, 13, 23, 15, 12, 18, 50, 5, 28, 27, 52, 46, 16, 40, 6, 33, 9, 41, 30, 54, 14, 36, 53, 17, 2, 11, 37, 42, 3, 8, 21, 25, 20, 34, 32, 35, 4, 43, 26, 38, 24, 10, 45, 31, 49, 44, 19, 51, 7, 1, 39, 47, 29] // 271Copy the code

Perfect ~ bronze player violence shuffling, simple straightforward, in the army cong straight enemy will head!!

Silver shuffle 📍

The silver player watched the bronze player and burst out laughing!

“Crazy line ~” (SB)

Copy the above code to the console run found, basically upset this deck of cards to wash 200 ~ 300 times! Because the further back, the greater the probability of generating random number repetition!

Only a crazy thread can wash so many times

So the silver players get to work! Remote sensing

Key words: [switch places].

Randomly split the cards into two piles, let them swap, then randomly split the cards into two piles, let them swap again, then randomly split the cards into two piles…… So repeat wash ten, twenty times, complete shuffle.

In fact, in real life, we play cards, and most players do it this way. It’s also called the Indian shuffle.

Code implementation:

// generate nums: let nums=[] for(let I =1; i<=54; I ++){nums.push(I)}  const shuffle = function(nums){ let radomNums = JSON.parse(JSON.stringify(nums)) for(let i = 0; i < 20; I++){let randIndex1 = randOneIndex() let randIndex2 = randOneIndex() if(randIndex2 < randIndex1){ RandIndex1 = randIndex1 + randIndex2 randIndex2 = randindex1-randindex2 randIndex1 = randIndex1-randindex2} let radomBlock = radomNums.slice(randIndex1,randIndex2 + 1) radomNums = Radomnums. slice(0,randIndex1). Concat (radomNums.slice(randIndex2,53)). Concat (radomBlock)} return radomNums} // From 0 to 53 An arbitrary integer is used as an array subscript; const randOneIndex= function() { return Math.floor(Math.random() * 54); } console.log(shuffle(nums)) // (54) [30, 9, 7, 28, 29, 39, 45, 46, 47, 48, 49, 50, 51, 52, 24, 25, 26, 27, 40, 42, 43, 44, 38, 31, 14, 8, 41, 22, 32, 19, 20, 1, 2, 10, 11, 12, 13, 16, 15, 53, 23, 3, 4, 5, 6, 21, 17, 18, 33, 34, 35, 36, 37, 42]Copy the code

Silver, eternal god! It only takes 20 shuffles to shuffle the cards!

Gold shuffle 💡

At this time, the gold player laughed again: “Ha ha, you slag silver, didn’t understand the topic!”

“Do you understand the meaning of the word shuffle? !”

Gold shuffle to find out:

A random result should cover all cases with equal probability;

Shuffle 54 cards, and the random result should cover all the cases so it should be 54 cards, A5454, 54! (54 classes) kind of random results.

Switch in pairs:

If you wash it once, you get n possible outcomes;

If you wash it twice, you get n times n minus 1;

Three washes will give n*(n-1)*(n-2) results;

.

After n washes, we are satisfied with: random results [covering all cases], and all random results [with equal probability].

So, you have to wash it 54 times to get there.

Code implementation:

// generate nums: let nums=[] for(let I =1; i<=54; I ++){nums.push(I)} // const shuffle = function(nums) {const radomNums = nums.slice(0); let n = radomNums.length; // the result is n! For (let I = 0; i < n; Rand = randOne(I, n-1); rand = randOne(I, n-1); [rand]] = [radomNums[rand], radomNums[rand], radomNums[I]]; } return radomNums; }; Const randOne= function(n, m) {return math.floor (math.random () * (m-n + 1)) + n; // Return math.floor (math.random () * (m-n + 1)) + n; }; console.log(shuffle(nums)) // (54) [39, 40, 11, 35, 1, 47, 33, 9, 44, 32, 31, 45, 41, 4, 51, 42, 8, 10, 16, 14, 18, 17, 13, 6, 34, 53, 48, 5, 15, 22, 38, 37, 49, 43, 3, 20, 26, 52, 30, 19, 7, 50, 12, 21, 46, 36, 23, 27, 28, 25, 2, 29, 24, 54]Copy the code

Platinum shuffle 🤣

Is the Internet cafe platinum god see above these younger brother, laugh out of pig call ~~~

If you go to the Internet and learn some strategies, you will not have heard of the Fisher-Yates shuffle algorithm on this problem!

Ideas:

Randomly generate an integer between 1 and 54 and replace it with the last bit of the array;

It then randomly generates an integer between 1 and 53 and replaces it with the penultimate second of the array.

Then generate a random integer between 1 and 52 and replace it with the third to last digit of the array.

.

Until a random integer (1) is generated between 1 and 1, replacing it with the first bit of the array (replacing itself);

To do so, the time complexity is O(n), and the probability of any card is 1/52, meet: random results cover all cases, random results appear with equal probability!

Mathematical proof: the probability that a card will be placed in the ith position is P, then P will be equal to the previous i-1 position did not pick this card and the ith position picked this card.

Code implementation:

// generate nums: let nums=[] for(let I =1; i<=54; // Const FYShuffle = function (nums) {const radomNums = nums.slice(0); let len = radomNums.length; while (len > 1) { let rand = Math.floor(Math.random() * len); len--; let temp = radomNums[len]; radomNums[len] = radomNums[rand]; radomNums[rand] = temp; } return radomNums; } console.log(FYShuffle(nums)) // (54) [47, 17, 33, 13, 37, 26, 20, 39, 45, 44, 25, 40, 49, 7, 36, 38, 6, 15, 31, 18, 52, 46, 28, 11, 43, 1, 22, 19, 53, 9, 14, 27, 35, 8, 51, 42, 50, 2, 23, 5, 30, 54, 4, 21, 29, 16, 10, 24, 48, 34, 32, 12, 41, 3]Copy the code

Diamond shuffle 😎

The diamond god stands up and exclaims: Riffle Shuffle, forever!

A lot of poker players do this in real life.

How it works: Split an array in half, merge it, and do it again and again.

Studies have shown that using the pigeon tail shuffle method [wash seven times] is the most effective shuffling technique! Who did the research? Google it)

Code implementation:

// generate nums: let nums=[] for(let I =1; i<=54; // Const RShuffle = function (arr) {let radomNums = nums.slice(0); for(let i = 0; i < 7; i++){ let randIndex = randOneIndex() let arr1 = radomNums.slice(0,randIndex) let arr2 = radomNums.slice(randIndex,55) radomNums = aryJoinAry(arr1 ,arr2) } return radomNums; Const aryJoinAry = function (ary,ary2) {var itemAry=[]; var minLength; If (ary.length>ary2.length){minLength=ary2.length; } else{ minLength=ary.length; Var longAry=arguments[0].length>arguments[1].length? arguments[0]:arguments[1]; For (var I = 0; i < minLength; I ++) {// Put an array into a temporary array itemary.push (ary[I]); ItemAry. Push (ary2[I])} // Concatenate the itemAry with the extra new array and return it. return itemAry.concat(longAry.slice(minLength)); } // Select an integer between 0 and 53 as an array subscript; const randOneIndex= function() { return Math.floor(Math.random() * 54); } console.log(RShuffle(nums)) // (54) [1, 4, 19, 2, 38, 51, 6, 37, 15, 9, 45, 43, 7, 52, 16, 21, 39, 53, 24, 26, 44, 54, 40, 5, 32, 10, 46, 22, 33, 27, 3, 11, 18, 28, 47, 12, 17, 29, 8, 13, 41, 30, 48, 14, 34, 31, 20, 23, 49, 35, 25, 42, 50, 36]Copy the code

Master shuffle 😏

The master smiled when he saw this.

The master said: “the card shuffle is important, but can not, the card shuffle, but also issued to their want cards? !”

Master, I understand! This is the lottery pool!!

Goal: After shuffling 54 cards, there is a 40% chance of drawing the range [1,10], a 20% chance of drawing the range [11,20], a 20% chance of drawing the range [21,30], a 15% chance of drawing the range [31,40], and a 5% chance of drawing the rest [41,54];

We implement an array of random numbers at the same time, output a probability array.

RadomNums = 8,6,33] [21,43,12,3,..., / / a total of 54 probabilityNums = [0.02, 0.015,..., 0.04, 0.04, 0.15] / / a total of 54, and 1Copy the code

Then get the value of the starting card through the following randomProbability:

function randomProbability(arr1, arr2) { var sum = 0, factor = 0, random = Math.random(); for(let i = arr2.length - 1; i >= 0; i--) { sum += arr2[i]; // statistical probability sump}; random *= sum; // generate probability random number for(let I = arr2.leng-1; i >= 0; i--) { factor += arr2[i]; if(random <= factor) return arr1[i]; // If the current probability is within the current probability range, return the current probability}; return null; } const yourCard = randomProbability(radomNums, probabilityNums) console.log(yourCard)Copy the code

King shuffle 👑

At this point, I saw the king figure in the height. He turned slowly around. Pointing to the ultimate shuffle secret with the scepter in hand: the random function! Holy and solemn!

Have you ever wondered what is the mechanism of the random function used everywhere?

If we break the generation rule of random, does that mean we break randomness?

ES5 explains the random function like this:

15.8.2.14 random ()

Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

The random() function produces values between [0,1) with roughly uniform distribution without parameters.

For further information, in Chrome V8 for Windows, the browser ends up calling rand_s, which is a random number generator that Windows provides. In other systems, it is also based on the current system to obtain high-precision random numbers. So the fundamental source of randomness is the power of the operating system.

However, MDN still says math. random is a pseudorandom number, which is not secure. The source of math. random is /dev/random, and the number of possible values is 2 ^ 64. The random algorithm is relatively simple, but ensures that the distribution is as random as possible.

Isn’t 2 to the 64th big enough? That’s right, it’s not enough! You know the full arrangement of 54 cards 54! The value is much greater than that. Therefore, it does not yet cover a large number of combinatorial scenarios.

So, are there really random numbers in the world? The king smiled

Currently, truly random numbers need to be collected from the real world, such as random.org, a site that generates random numbers by collecting atmospheric noise. 😮

There are also quantum random numbers. The principle is that LED emits a random number of photons, CMOS captures the noise of the light source to generate a random sequence, and the quantum chip obtains a random number by measuring the quantum state of light, and further encrypts the information.

It has to be said that generating true random numbers is a very meaningful thing. At least in the current world has not proved P ≠ NP, it is very meaningful!!

Ideal world 🌅

Order and disorder, or entropy increase and entropy decrease, is a big problem.

We usually know so many kinds of sorting algorithm, should also know shuffling algorithm (out-of-order algorithm).

Imagine if you were God, and you were designing a human society, and you wanted the human community to be confused and confused at times, how would you mess with the various causes? No matter how hard humans try, they can’t see through your rules of disruption. Maybe only God can do that

Perhaps our constant process of exacting dimensions is the process of finding out the rules of god……

Just as Bengua had always thought that a second was a second, not knowing that it was actually defined as: the time required for 9192631770 natural microwave oscillations of the cesium atom……

Ok, that’s it. It is envisaged that there will be more discussions on ordered disorder, rational and irrational numbers, P/NP problems in the future

Please like 👍 and follow 👀 in the comments 💬

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~