# [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

1. We randomly select a number from the array and exchange the number at the last position of the current array
2. Remove the array at the end of the exchange and proceed to step 1
3. 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

## More related blog posts

[youth training camp] teacher Yueying told me the three principles of writing JavaScript well - each should take his own responsibility

[youth training camp] teacher Yueying told me the three principles of writing JavaScript - component encapsulation

[youth training camp] teacher Yueying told me the three principles of writing JavaScript well - process abstraction

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

Keywords: Javascript Algorithm

Added by dhrosti on Mon, 25 Oct 2021 06:34:02 +0300