📻 preface

In our daily life, we always come across the topic of fairness. For example, how can a prize be distributed fairly among several people? Or maybe there’s a raffle wheel at the annual meeting. What makes it fair?

In this next article, we’ll talk about fairness in shuffling cards. Find out

A, 🎙️ demand analysis – shuffle problem

Sometimes in our spare time may play the fight landlord and so on poker game, but this poker how to shuffle, can not lose fairness?

So, let’s talk about an implementation from the shallow to the deep.

2. 💿 implementation version

Version 1: Conventional thinking

First attach the code:

JS code:

const cards = [0.1.2.3.4.5.6.7.8.9];

function shuffle(cards) {
  return [...cards].sort(() = > Math.random() > 0.5 ? -1 : 1);
}

console.log(shuffle(cards)); // [5, 4, 3, 2, 1, 9, 0, 6, 8, 7]
Copy the code

If you want to be fair, then many of your friends at first think of random shuffling. But math.random () is not really random.

Its randomness is related to the original position, it is random to exchange the position of the original two numbers, and the uncertainty of whether this position will produce exchange is also great, so it cannot achieve real fairness.

2. Version 2: Verify fairness

First attach the code:

JS code:

const cards = [0.1.2.3.4.5.6.7.8.9];

function shuffle(cards) {
  return [...cards].sort(() = > Math.random() > 0.5 ? -1 : 1);
}

const result = Array(10).fill(0);

for(let i = 0; i < 1000000; i++) {
  const c = shuffle(cards);
  for(let j = 0; j < 10; j++) { result[j] += c[j]; }}console.log(result);
Copy the code

Let’s see why it’s unfair based on the example of version one. First look at the print effect:

As you can see, if this algorithm were fair, it would be fairly average from the first to the last, and in this algorithm, the lower the number, the higher the number, so there’s something obviously wrong with this randomness. In general, if you use this algorithm, the students at the bottom of the line will have a lower probability of winning than the students at the top.

Version 3: Rules of exchange

First attach the code:

JS code:

const cards = [0.1.2.3.4.5.6.7.8.9];

function shuffle(cards) {
  const c = [...cards];
  for(let i = c.length; i > 0; i--) {
    const pIdx = Math.floor(Math.random() * i);
    [c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
  }
  return c;
} 

// Verify that it is fair
const result = Array(10).fill(0);

for(let i = 0; i < 10000; i++) {
  const c = shuffle(cards);
  for(let j = 0; j < 10; j++) { result[j] += c[j]; }}console.log(shuffle(cards));
console.log(result);
Copy the code

Based on the flaws of the previous two versions, let’s implement a fair approach. The algorithm above, which is O(n), works by taking a random number in an ordered array, putting it in the last place, then taking a random number, swapping it in the last place, and so on. Specific ideas are shown in the figure below:

Here is the console print effect:

As you can see, the numbers printed by the console are relatively average, not very different from one another. So, this algorithm is fair.

3. 📺 Online

Online address for the above three versions:

  • Version 1: Conventional thinking
  • Version 2: Verify fairness
  • Version 3: Rules of exchange

4. 📹 Conclusion

In the above article, we first discuss the unfairness of random shuffle, and then reintroduce a new exchange law to realize the fairness of shuffle. Do not know whether we have a further understanding of the shuffling problem?

If you think this article is helpful to you, you might as well like to support yo ~~😉

📸 previous recommendation

👉 Follow the steps of moon Shadow big guy, let’s learn how to write good JS (1)

👉 Follow the steps of moon Shadow big guy to learn how to write good JS (2)

👉 every day in front of the traffic lights shuttle line, how about their own to achieve a traffic light?

👉 idempotent problem vs how to determine if it is a power of 4