Когда три года назад взорвались красные конверты WeChat, я восполнил принцип распространения, стоящий за этим, и написал демо на C. Теперь я думаю, что решение на тот момент было в определенной степени интересным, поэтому я обогатил его и переписал на js. .
Правила, которым должен соответствовать алгоритм красного конверта, следующие:
- Сумма схваченной всеми суммы равна сумме красного конверта, которая не может быть больше или меньше;
- У всех есть равные шансы получить сумму;
- Сумма, которую все получают, больше 0.
Первая картинка, которая пришла мне в голову, была:排排坐，分果果.
Итак, принцип распределения следующий:
Все люди сначала заняли свои места в порядке захвата красных конвертов, образовали круг и разделили сумму поровну между всеми, а затем每人同时将自己手中的金额随机抽出部分给左右临近的2个人，但保证手头至少剩余1单位的金额, выполните задание.
- Поскольку обменное распределение производится на основе общей суммы, выполняется Правило 1;
- Так как обмен случайной суммы с одинаковыми условиями осуществляется на основе равной доли суммы, второе правило выполняется;
- Поскольку случайное распределение гарантирует, что по крайней мере 1 единица зарезервирована, третье правило выполняется.
Затем запустите описанный выше процесс
- Получить общее распределение
Поскольку слабо типизированные языки могут изменять непредсказуемые входные параметры, вы должны быть умны, чтобы фильтровать, когда вы получаете цифру общей суммы.Здесь мы используем тот, который написал бог jonschlinkert.is-numberФункция используется для определения того, является ли входной параметр числом, в противном случае ему присваивается значение 0; кроме того, чтобы избежать проблемы точности десятичной операции в js, для сложения и вычитания в этом алгоритме используются только целые числа, что то есть, десятичные дроби помещаются вместо целых чисел (умножение кратных), операция Затем уменьшить его обратно к исходному кратному (разделить кратное).
class RandomSplit{
constructor(num){
// 实际总数
this.num = this.getNum(num);
// 放大倍数
try{
this.multiple = this.num.toString().split('.')[1].length;
}catch(e){
this.multiple = 0;
}
// 用于整数运算的总数
this.calcNum = this.num * Math.pow(10, this.multiple);
}
// 判断是否为number（取用至“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;
}
// 获取数字
getNum(num, defaultNum = 0){
return this.isNumber(num) ? (+num) : defaultNum;
}
}
- Рассадив в круг, делим сумму на количество порций
Глядя на слово «кольцо», кажется, что нужно использовать двусторонний кольцевой связанный список.Для экономии кода используется только одномерный массив для имитации его эффекта, а подключение данных может выполняться в начале и в конце. массива. В этом алгоритме атомарной единицей всех чисел, используемых для распределения обмена, является целое число 1, поэтому деление также необходимо разделить на целые числа, такие как сумма15поровну6порция, сначала на каждую порцию2(Math.floor(15/6)===2), осталось3(15%6===3), чтобы сделать вероятность, используемую в расчете позже, максимально возможной, нам нужно положить оставшиеся3Единицы равномерно разбросаны по 6 копиям, и аналогичный процесс выглядит следующим образом:
Точно так же, если вы хотите более точно разделить поровну, вы можете указать количество цифр точности, затем увеличить общее число на количество цифр, а затем уменьшить количество цифр точности для каждой части после того, как целое число будет разделено поровну. .
Таким образом, функция усреднения выглядит следующим образом:
// 均分份数， 均分精度， 是否直接返回放大后的整数
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);
// 份数超过放大后的计算总数，即不够分的情况
if(n > calcNum){
return [];
}else{
let index = 0;
// 平均数
let avg = Math.floor(calcNum / n);
// 剩余数
let rest = calcNum % n;
// 剩余数填充间隔
let gap = Math.round((n-rest) / rest) + 1;
// 原始平均数组
let result = Array(n).fill(avg);
//
while (rest > 0) {
index = (--rest) * gap;
result[index>=n ?(n-1) : index]++;
}
// 返回放大后的结果数组
if(isInt){
return result;
}
// 返回处理完符合精度要求的结果数组
return result.map((item) => {
return (item / Math.pow(10, this.multiple + precision));
});
}
}
Результаты теста следующие:
- Случайный обмен соседями
После получения средней суммы каждая позиция сначала случайным образом выдает сумму, которая должна быть выдана, которая больше или равна 0 и меньше своей исходной суммы, а затем случайным образом делит сумму на две части и отдает их соседним слева и правильные позиции.
// 随机划分的份数， 划分精度
split(n, precision){
n = Math.floor(this.getNum(n));
precision = Math.floor(this.getNum(precision, 0));
// 均分
let arr = this.average(n, precision, true);
let arrResult = arr.concat();
for (let i = 0; i < arr.length; i++) {
//给出的总额
let num = Math.floor(Math.random() * arr[i]);
// 给左邻的数额
let numLeft = Math.floor(Math.random() * num);
// 给右邻的数额
let numRight = num - numLeft;
// 首尾index处理
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;
}
// 缩小至原尺度
return arrResult.map((item) => {
return (item / Math.pow(10, this.multiple + precision));
});
}
Результаты теста следующие:
Общий тест результатов
использоватьEchartsНарисуйте результат случайного распределения, разделите сумму 100 на 10 частей, точность равна 1, абсцисса — это позиция заказа, а ордината — выделенная сумма:
Равна ли вероятность получить сумму по каждой позиции? Следующее изображение является результатом 100 случайных назначений, и среднее из 100 назначений для каждой позиции отмечено красным:
Как насчет выделения 1000 раз?
Можно видеть, что чем больше случайных распределений, тем средняя сумма, полученная каждой последовательной позицией, будет стабильной вокруг равномерно распределенной суммы, и справедливость была подтверждена; в то же время, поскольку каждая позиция может получить только сумму, обмененную между две соседние позиции, так что сумма в любой позиции в результате раздачи не будет превышать среднюю сумму в 3 раза (то есть вы и за волосы не тянете, и при этом получаете помощь соседей), так что вы можете контролировать максимальную сумму в результате случайного распределения, чтобы она не была слишком высокой.
Отверстие в мозгу здесь, что, если левое и правое не поменять местами рядом? Как насчет изменения правил обмена?
-
和除自己外的随机位置的两位进行随机数额交换？Вероятностно говоря, это эквивалентно предыдущему... -
只和自己左右或者右边的位置进行随机数额交换？Результаты раздачи по-прежнему справедливы, но максимальная сумма не будет превышать среднюю сумму в 2 раза. -
每个位置随机左右一边然后进行随机数额交换？Опять же рандом, это честно, а максимальная сумма все равно меньше чем в 3 раза от средней суммы (такое чувство, что она может заменить предыдущую схему, а так же может удвоить линейную сложность кстати, моя статья будет переписана ?! (°ー°〃)) -
谁说只能挑2个进行交换？3个4个5个一起来行不行？ОК... Если отбор честный, то и результат раздачи будет честным, но максимальная сумма положительно связана с количеством обменов, но чем больше сумма, тем вероятность ее получения резко снизится.
Стоп, стоп, подумай, боюсь, я не смогу его наполнить _(:з"∠)_
Так что же еще эта штука может делать, кроме как раздавать бонусы?
Я использовал его, чтобы написать индикатор выполнения без внутренних данных, и казалось, что он действительно загружается для вас...
Другое... Я надеюсь, вы можете использовать свое воображение
Наконец )
初入掘金，不足之处望海涵，转载烦请注明出处