Блог

Допустим, есть 100 люди и $120 . Какова формула, которая может разделить ее на случайные суммы, чтобы каждый человек что-то получал?

В этом сценарии один человек может получить произвольную сумму, например $0.25 , кто-то может получить $10 , кто-то может получить $1 , но каждый что-то получает. Какие-нибудь советы?

Таким образом, в Javascript может быть сгенерирован массив из 100, и эти случайные числа будут в них, но они будут складываться до 100

Чтобы получить результат с минимально возможной суммой в 1 цент, используя простые средства, вы можете сгенерировать 100 случайных значений, найти их сумму S, затем умножить каждое значение на 120.0/Sum с округлением до целых центов, снова получить сумму. Если есть некоторый избыток (несколько центов), распределите его случайным лицам.

Пример на Python для 10 человек и 12 $. 1 и overall-num позволяет избежать нулевых сумм:

 import random

overall = 1200
num = 10
amounts = [random.random() for _ in range(num)]
asum = sum(amounts)
for i in range(num):
    amounts[i] = 1   int(amounts[i]*(overall-num) / asum)
asum = sum(amounts)
for i in range(overall - asum):
    amounts[random.randint(0,9)]  = 1

print(amounts, sum(amounts))

>>[163, 186, 178, 152, 89, 81, 169, 90, 17, 75] 1200
 

Другой способ (справедливое распределение вариантов в математическом смысле), как заметил Аки Суйхконен в комментариях, заключается в использовании случайного выбора из массива позиций разделителей (с перетасовкой) для реализации (мое первое предложение, но я предполагал слишком сложную реализацию ранее):

 put 12000 one-cent coins in row
put 99 sticks (dividers) between them, in 11999 spaces between coins
give coins between k and k 1 stick to k-th person
 

Реализация на Python:

 arr = [i for i in range(overall-1)]
divs = [0]   sorted(random.choices(arr, k=num-1))   [overall]
amounts = [(divs[i 1]-divs[i]) for i in range(num)]
print(amounts, sum(amounts))

>>>[17, 155, 6, 102, 27, 222, 25, 362, 50, 234] 1200
 

И просто чтобы предоставить другой способ сделать это, назначьте каждому случайное число, затем нормализуйте, чтобы сумма складывалась правильно. Это должно быть достаточно эффективным, O(countPeople) независимо от того, сколько денег мы делим или насколько точно мы их делим.

Вот решение на JavaScript, которое при желании также будет обрабатывать округление до ближайшего пенни. К сожалению, хотя маловероятно, что это не даст кому-то денег, это возможно. Это можно решить либо путем извлечения одного пенни на человека и предоставления им этого, либо путем проверки, не удалось ли вам раздать деньги, и повторного запуска.

 function distributeRandomly(value, countPeople, roundTo) {
    var weights = [];
    var total = 0
    var i;

    // To avoid floating point error, use integer operations.
    if (roundTo) {
        value = Math.round(value / roundTo);
    }
    
    for (i=0; i < countPeople; i  ) {
        weights[i] = Math.random();
        total  = weights[i];
    }

    for (i=0; i < countPeople; i  ) {
        weights[i] *= value / total;
    }
    
    if (roundTo) {
        // Round off
        total = 0;
        for (i = 0; i < countPeople; i  ) {
            var rounded = Math.floor(weights[i]);
            total  = weights[i] - rounded;
            weights[i] = rounded;
        }

        total = Math.round(total);

        // Distribute the rounding randomly
        while (0 < total) {
            weights[Math.floor(Math.random()*countPeople)]  = 1;
            total -= 1;
        }

        // And now normalize
        for (i = 0; i < countPeople; i  ) {
            weights[i] *= roundTo;
        }
    }

    return weights;
}

console.log(distributeRandomly(120, 5));
console.log(distributeRandomly(120, 6, 0.01));
 

Каким должно быть целевое распределение?

MBo дает AFAIK распределение Пуассона (с оригинальным подходом случайного размещения 99 разделителей в диапазоне от 1 до 11999). Другим вариантом было бы сначала разделить суммы равномерно, затем для каждых двух участников перераспределить богатство, передав случайную сумму от 0 до 1,19 доллара от одного человека другому.

Повторите несколько раз, если недостаточно, чтобы максимальная сумма была всего в 2 раза больше ожидаемой.

Вам нужно многочленное распределение. Я разделил 12000 вместо 120, чтобы разрешить центы.

 var n = 100;
var probs = Array(n).fill(1/n);
var sum = Array(n).fill(0);

for(var k=0; k < 12000; k  ){
    var i = -1;
    var p = 0;
    var u = Math.random();
    while(p < u){
        i  = 1;
        p  = probs[i];
    }
    sum[i]  = 1;
}

sum = sum.map(function(x){return x/100;});
console.log(sum);
1.26,1.37,1.28,1.44,1.31,1.22,1.2,1.27,1.21,1.37,1.05,1.17,0.98,1.13,1.18,1.44,0.94,1.32,1.03,1.23,1.19,1.13,1.13,1.32,1.36,1.35,1.32,1.04,1.1,1.18,1.18,1.31,1.17,1.13,1.08,1.11,1.19,1.31,1.2,1.1,1.31,1.22,1.15,1.09,1.27,1.14,1.06,1.23,1.21,0.94,1.32,1.13,1.29,1.25,1.13,1.22,1.13,1.13,1.1,1.16,1.12,1.11,1.26,1.21,1.07,1.19,1.07,1.46,1.14,1.18,0.96,1.21,1.18,1.2,1.18,1.2,1.33,1.01,1.31,1.16,1.28,1.21,1.42,1.29,1.04,1.28,1.12,1.2,1.23,1.39,1.26,1.03,1.27,1.18,1.11,1.31,1.46,1.15,1.23,1.21
 

Одним из методов было бы работать в копейках и давать каждому по одному для начала, а затем случайным образом выбирать последующих людей, чтобы давать дополнительные копейки, пока у вас не закончатся копейки. Это должно дать среднее значение 1.20 и стандартное отклонение 1 . Код относительно прост:

 const stats = (ns, Σ = ns .reduce ((a, b) => a   b, 0), μ = Σ / ns.length, σ2 = ns .map (n => (n - μ) ** 2) .reduce ((a, b) => a   b), σ = Math .sqrt (σ2)) => ({sum: Math .round(Σ), mean: μ, stdDev: σ, min: Math .min (...ns), max: Math .max (...ns)})

const randomDist = (buckets, total, {factor = 100, min = 1} = {}) => 
  Array (total * factor - buckets * min) .fill (1) .reduce (
    (res, _) => {res [Math.floor (Math.random() * buckets)]  = 1 ; return res},
    Array (buckets) .fill (min)
  ) .map (n => n / factor)


const res = randomDist (100, 120)
console .log (stats (res))
console .log (res) 

 .as-console-wrapper {max-height: 100% !important; top: 0} 

Мы принимаем количество сегментов и общую сумму для включения. Мы также необязательно принимаем коэффициент, который мы используем для преобразования в наш минимальный шаг, и минимальное значение, которое получает каждый. ( stats Функция предназначена только для целей отчетности.)

С помощью этого метода разброс, вероятно, довольно мал. Хотя теоретически для человека возможно получить $.01 или $119.01 , шансы крайне малы. Мы можем изменить это, случайным образом выбирая, сколько добавить человеку на каждом шаге (а не просто использовать один пенни). У меня нет большого опыта в статистике, чтобы оправдать этот механизм, но он кажется относительно надежным. Для этого потребуется еще один необязательный параметр, который я вызываю block , который является наибольшим размером блока, который мы будем распространять. Это будет выглядеть так:

 const {floor, exp, random, log, min, max, sqrt} = Math
const stats = (ns, Σ = ns .reduce ((a, b) => a   b, 0), μ = Σ / ns.length, σ2 = ns .map (n => (n - μ) ** 2) .reduce ((a, b) => a   b), σ = sqrt (σ2)) => ({mean: μ, stdDev: σ, min: min (...ns), max: max (...ns)})

const randomDist = (buckets, total, {factor = 100, minimum = 1, block = 100} = {}) => {
  const res = Array (buckets) .fill (minimum)
  let used = total * factor - buckets  * minimum
  while (used > 0) {
    const bucket = floor (random () * buckets)
    const amount = 1   floor (exp (random () * log ((min (used, block)))))
    used -= amount
    res [bucket]  = amount
  }
  return res .map (r => r / factor)
}

const res1 = randomDist (100, 120)
console .log (stats (res1))
console .log (res1)

const res2 = randomDist (100, 120, {block: 500})
console .log (stats (res2))
console .log (res2) 

 .as-console-wrapper {max-height: 100% !important; top: 0} 

Обратите внимание, что когда мы переключаемся с размера блока по умолчанию 100 на 500 , мы переходим от статистики типа

 {mean: 1.2, stdDev: 7.48581986157829, min: 0.03, max: 3.52}
 

для таких, как это:

 {mean: 1.2, stdDev: 17.75106194006432, min: 0.01, max: 10.39}
 

и если мы перейдем к 10 , это может выглядеть так

 {mean: 1.2, stdDev: 2.707932606251492, min: 0.67, max: 2.13}
 

Вы можете поиграть с этим параметром, пока он не получит распределение, похожее на то, что вы хотите. (Если вы установите для него значение 1 , оно будет иметь то же поведение, что и первый фрагмент.)