[youth training camp] teacher Yueying told me four skills to write JavaScript well - to ensure correctness

How to write JavaScript well is a question that every front-end engineer has been thinking about. Teacher Yueying told us some principles of writing JavaScript well, and also taught us some skills of how to write JavaScript well. Today, let's continue to learn JavaScript from teacher Yueying~~

start

When we write code, the most important thing is to ensure the correctness of our code. However, in some cases, the code can run normally and looks quite right, but in fact, the code may not be so correct~

Let's look at an example

shuffle algorithm

Let you implement a shuffle algorithm. How will you implement it? You will soon think that we can directly sort the array randomly, that is, shuffle. The code is as follows

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

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

Running several more times seems to have a good effect, which really disrupts the order

Is this algorithm really correct? Or is this algorithm really fair?

Verify correctness

Let's verify the correctness of this shuffle algorithm. How to verify it?

We repeat the shuffle procedure a million times. The result array is used to record the sum of the numbers in each position. If this is a fair algorithm, the numbers in the result array should be very similar.

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);

The result is

[3863812, 3862770, 4544657, 4648808, 4669379, 4364000, 4362095, 4722847, 4852688, 5108944]

It can be seen that this result is increasing, and the difference between the sum of all numbers in the first and last positions is relatively large, that is, the larger the number, the greater the probability of appearing behind the array. The probability that each element is arranged at each location is different, which is an unfair algorithm.

How to solve this problem?

Solution 1: wash more times

Wash twice

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

for (let i = 0; i < 1000000; i++) {
  const c = shuffle(shuffle(cards));
  for (let j = 0; j < 10; j++) {
    result[j] += c[j];
  }
}

console.log(result);

[4431933, 4414334, 4501168, 4514001, 4527342, 4493793, 4496849, 4537253, 4540943, 4542384]

Wash three times

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

for (let i = 0; i < 1000000; i++) {
  const c = shuffle(shuffle(shuffle(cards)));
  for (let j = 0; j < 10; j++) {
    result[j] += c[j];
  }
}

console.log(result);

[4487963, 4491386, 4495428, 4499063, 4494726, 4505270, 4498303, 4510195, 4508869, 4508797]

It can be seen that after washing several times, the numbers in the result array are basically the same, that is, our algorithm is relatively fair!

Solution 2: random sampling

Repeated shuffling does not solve the problem at the algorithm level. We hope to fundamentally solve the problem by modifying the shuffling algorithm

The reason why the previous algorithm has problems is that we use the sort method. When exchanging two pairs, they are exchanged nearby, so the exchange position is not random enough

We use random sampling method to shuffle

We randomly select a number from the array and exchange the number at the last position of the current array
Remove the array at the end of the exchange and proceed to step 1
Until all the numbers are exchanged

Algorithm implementation

function shuffle(cards) {
  const c = [...cards];
  // Traversal array in reverse order
  for (let i = c.length; i > 0; i--) {,
    // Pick a location at random
    const pIdx = Math.floor(Math.random() * i);
    // Exchange the element at the selected position with the element at the end of the array
    [c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
  }
  return c;
}

It is equivalent to the model of touching the ball without putting it back in combinatorial mathematics. Assuming that there are n balls, it is easy to prove that the probability of this algorithm for each ball is 1/n through mathematical induction

Verify the algorithm with the above verification method

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);

Results obtained

[4498337, 4502249, 4502001, 4498385, 4504714, 4500172, 4498057, 4502210, 4498232, 4495643]

It can be seen that the numbers are very similar and uniform, so this algorithm is fair and correct

application

luck draw

For example, if we want to draw a lottery, we can directly take an element at any position

Math.floor(Math.random() * length)

However, our lucky draw is a process, such as drawing out the first prize, second prize, third prize, lucky prize and so on. We need to encapsulate it and adopt the shuffle algorithm above

By changing the function to a generator and the return to yield, you can implement a partial shuffle or use it as a lucky draw

function* shuffle(items) {
  items = [...items];
  for (let i = items.length; i > 0; i--) {
    const idx = Math.floor(Math.random() * i);
    [items[idx], items[i - 1]] = [items[i - 1], items[idx]];
    yield items[i - 1];
  }
}

You can show it all

let items = [1, 2, 3, 4, 5, 6, 7, 8, 9];
items = shuffle(items);
console.log(...items); // 7 1 2 8 5 3 9 4 6

You can also select only part to realize the function of partial shuffle or lucky draw

Five of the 100 numbers were randomly selected

let items = [...new Array(100).keys()];

let n = 0;
// Five of the 100 numbers were randomly selected
for (let item of shuffle(items)) {
  console.log(item);
  if (n++ >= 5) break;
}
// 24 62 60 16 42 21

Bonus package

In the red envelope grabbing function in APP, the algorithm of random dividend package is carried out internally

In order not to happen, after a random score, one red packet is too large, resulting in insufficient scores for the remaining red packets, the following scoring method can be adopted, that is, after each division, the largest red packet existing shall be selected to continue the division, so as to ensure that the red packets can be divided enough

function generate(amount, count){
  let ret = [amount];
  
  while(count > 1){
    //Select the largest piece for segmentation
    let cake = Math.max(...ret),
        idx = ret.indexOf(cake),
        part = 1 + Math.floor((cake / 2) * Math.random()),
        rest = cake - part;
    
    ret.splice(idx, 1, part, rest);
    
    count--;
  }
  return ret;
}

The above division method will lead to a very uniform red envelope each time

Sometimes, in order to increase the fun of grabbing red envelopes, we don't want our red envelopes to be so average

For example, giving 100 yuan to 10 people is equivalent to cutting on a (0100.00) number axis and randomly cutting nine knives in different positions,

Therefore, it can be converted into our shuffle program. Nine positions are randomly selected from the 10000 positions between 0 and 100.00, and the red envelope is divided into ten parts, so that the red envelope will not be distributed so evenly

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]];
    yield c[i - 1];
  }
}

function generate(amount, count){
  if(count <= 1) return [amount];
  const cards = Array(amount - 1).fill(0).map((_, i) => i + 1);
  const pick = shuffle(cards);
  const result = [];
  for(let i = 0; i < count; i++) {
    result.push(pick.next().value);
  }
  result.sort((a, b) => a - b);
  for(let i = count - 1; i > 0; i--) {
    result[i] = result[i] - result[i - 1];
  }
  return result;
}

summary

When we write the program, we must ensure its correctness!

Using sort method to shuffle cards randomly may lead to unfair algorithm

Programming VIP