Three years ago, when wechat red envelope exploded, I imagined the distribution principle behind it and wrote a demo with C. Now I think the solution at that time is interesting, so I enriched and completed it and rewrote it with JS.
The red envelope algorithm must meet the following rules:
- The sum of all the money grabbed is equal to the red envelope amount, no more than, no less than;
- Everyone has an equal chance of getting the money;
- Everyone gets more than 0.
The first picture I imagine is: rows of rows, rows of rows.
So the distribution principle is as follows:
People take their seats in order to grab the red envelope, form a circle, divide the amount equally among each person, and thenAt the same time, each person will randomly draw out part of the amount in his hand to the left and right adjacent two people, but ensure that there is at least 1 unit of amount left in handTo complete the assignment.
- Since the exchange allocation is made on the basis of the total amount, rule 1 is satisfied;
- The random amount exchange under the same conditions is carried out on the basis of equal amount, so rule 2 is met.
- Since at least 1 unit of money is guaranteed to be retained in the random allocation, rule 3 is satisfied.
Then start implementing the above process
- Get total allocation
Because of the unshakable input parameter of weakly typed language, when you get the total amount, you must be smart to do the filtering. Here we use the is-number function written by Jonschlinkert to determine whether the input is a number, otherwise set it to 0. In addition, in order to avoid the accuracy of JS small number operation, the algorithm only uses integers for addition and subtraction, that is, the decimal is put in place integer (multiple), and then reduced back to the original multiple (divide multiple) after operation.
class RandomSplit{
constructor(num){
// The actual total
this.num = this.getNum(num);
// Magnification
try{
this.multiple = this.num.toString().split('. ') [1].length;
}catch(e){
this.multiple = 0;
}
// The total number of integer operations
this.calcNum = this.num * Math.pow(10.this.multiple);
}
// Check whether the value is number (select "is-number")
isNumber(num){
let number = +num;
if((number - number) ! = =0) {return false;
}
if(number === num){
return true;
}
if(typeof num === 'string') {if(number === 0 && num.trim() === ' ') {return false;
}
return true;
}
return false;
}
// Get the number
getNum(num, defaultNum = 0) {return this.isNumber(num) ? (+num) : defaultNum; }}Copy the code
- Ring seating, divide the total by share
Look at the word “ring”, as if you need to use a bidirectional circular linked list, in order to save code, only a one-dimensional array to simulate its effect, the array at the beginning and end of the data connection can be done. In this algorithm, all the atomic units used to allocate the swapped numbers are integers 1, so the equalizations need to be equally divided into integers. For example, the total number of 15 is divided into 6 parts, each of which is divided into 2 first (math.floor (15/6)===2), and the remaining 3 (15%6===3). In order to make the probabilities used for subsequent calculations as even as possible, We need to evenly spread the remaining 3 units into the 6 pieces, similar to the following process:
Similarly, if you want to evenly divide more accurately, you can provide precision bits, and then enlarge the total number by that bit. After evenly dividing the integers, each piece is reduced by that precision bit.
So the equipartition function is as follows:
// Whether to return the enlarged integer directly
average(n, precision, isInt){
precision = Math.floor(this.getNum(precision, 0));
n = Math.floor(this.getNum(n));
let calcNum = this.calcNum * Math.pow(10, precision<0 ? 0 : precision);
// The number of copies exceeds the calculated total after amplification, i.e. the case of insufficient points
if(n > calcNum){
return [];
}else{
let index = 0;
/ / the mean
let avg = Math.floor(calcNum / n);
/ / the remaining number
let rest = calcNum % n;
// The remaining number fills the interval
let gap = Math.round((n-rest) / rest) + 1;
// The original average array
let result = Array(n).fill(avg);
//
while (rest > 0) {
index = (--rest) * gap;
result[index>=n ?(n- 1) : index]++;
}
// Returns an enlarged array of results
if(isInt){
return result;
}
// Returns an array of results that meet the accuracy requirement
return result.map((item) = > {
return (item / Math.pow(10.this.multiple + precision)); }); }}Copy the codeThe test results are as follows:
- Adjacent random exchange
After getting the equal amount, each position first randomly calculates the amount to be given, which is greater than or equal to 0 and less than its initial amount, and then randomly divides the amount into two parts, respectively to the adjacent left and right positions.
// The number of partitions randomly divided, the partition precision
split(n, precision){
n = Math.floor(this.getNum(n));
precision = Math.floor(this.getNum(precision, 0));
/ / split
let arr = this.average(n, precision, true);
let arrResult = arr.concat();
for (let i = 0; i < arr.length; i++) {
// The total amount given
let num = Math.floor(Math.random() * arr[i]);
// The amount given to the left neighbor
let numLeft = Math.floor(Math.random() * num);
// The amount given to the right neighbor
let numRight = num - numLeft;
// start and end index processing
let iLeft = i===0 ? (arr.length- 1) : (i- 1);
let iRight = i===(arr.length- 1)?0 : (i+1);
arrResult[i] -= num;
arrResult[iLeft] += numLeft;
arrResult[iRight] += numRight;
}
// Scale down to the original size
return arrResult.map((item) = > {
return (item / Math.pow(10.this.multiple + precision));
});
}
Copy the codeThe test results are as follows:
Overall results test
Using Echarts to draw random distribution results, divide 100 amounts into 10 pieces with accuracy of 1, abscissa is the sequential position and ordinate is the amount allocated:
Is each position equally likely to get the amount? The figure below is the result of 100 random assignments, with the average of the 100 assignments for each position in red:
How about 1,000 times?
It can be seen that the more times of random allocation, the average amount of each position will be stable around the average amount of allocation, fairness is verified. At the same time, because each position can only get the exchange of the amount of two neighboring positions, so the amount of any position in the distribution result will not exceed 3 times the average amount (that is, he does not pay a dime, and at the same time, he gets the help of his neighbors), so that the maximum amount in the random distribution result can be controlled not to be too high.
Imagination is coming. What if it’s not swapping left and right? What happens if you change the rules of exchange?
Swap random amounts with two random positions other than yourself?In terms of probability, this is the same as before…You just swap random amounts to your left and right or to your right?The distribution would still be fair, but the maximum amount would not be more than twice the averageEach position is randomly left and right and then you swap random amounts, right?Double 叒 random, or fair, the maximum amount or less than 3 times the average amount (feel like it can replace the previous scheme, but also can incidentally reduce the linear complexity twice, MY article to rewrite? ! (° * * “))Who says you can only pick 2 to swap? How about three, four, and five?Line… If you pick fairly, the distribution is fair, but the maximum number is positively correlated with the number of swaps, but the higher the number, the probability of getting something decreases dramatically.
Stop, stop, stop, reflect on it, I’m afraid I want to fill more holes _(:з “_
So what’s this thing for other than bonus packs?
I’ve used it to write a progress bar with no back-end data, and it seems like it’s actually loading you…
The other… I hope you use your imagination
Finally (˙-˙)
First into the gold, the lack of hope haihan, reproduced please indicate the source