Разделите число на три группы с ограничениями - PullRequest
Новая
       22

Разделите число на три группы с ограничениями

3 голосов
/ 15 ноября 2011

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

Например, скажем, мое случайно сгенерированное число равно 1000, и янужно разделить его на сегменты a, b и c. 

These ranges are only an example. See my edit for possible ranges.
Bucket a may only be between 10% - 70% of the number (100 - 700)
Bucket b may only be between 10% - 50% of the number (100 - 500)
Bucket c may only be between 5% - 25% of the number (50 - 250)
a + b + c must equal the randomly generated number

Вы хотите, чтобы назначенные суммы были полностью случайными, поэтому существует равный шанс того, что интервал достигнет своего максимума, как интервал c в дополнение ккак равный шанс того, что все три сегмента будут около среднего значения в процентах.

РЕДАКТИРОВАТЬ: Скорее всего, всегда будет верно следующее: нижний предел a + b + c <100%, верхний предел a + b +с> 100%.Эти проценты предназначены только для указания приемлемых значений a, b и c.В случае, когда a равно 10%, в то время как b и c являются их максимумами (50% и 25% соответственно), числа должны быть переназначены, так как общее количество не будет равно 100%.Это именно тот случай, которого я пытаюсь избежать, найдя способ назначить эти числа за один проход.

Я бы хотел найти способ случайного выбора этих чисел в пределах их диапазона за один проход.

Ответы [ 2 ]

2 голосов
/ 16 ноября 2011

Проблема эквивалентна выбору случайной точки в N-мерном объекте (в вашем примере N = 3), объект определяется уравнениями (в вашем примере): 

0.1  <= x  <= 0.7
0.1  <= y  <= 0.5
0.05 <= z  <= 0.25
x + y + z   = 1 (*)

Ясноиз-за последнего уравнения (*) одна из координат является избыточной, то есть выбор значений для x и y диктует z.

Eliminating (*), а одно из других уравнений оставляет нас с (N-1)-мерная коробка, например 

0.1 <= x  <= 0.7
0.1 <= y  <= 0.5

, которая сокращается неравенством 

0.05 <= (1 - x - y) <= 0.25 (**)

, полученным из (*), и уравнением для z.По сути, это диагональная полоса через прямоугольник.

Чтобы результаты были однородными, я бы просто повторно выбрал (N-1) -мерный прямоугольник и принял бы первую точку выборки, которая удовлетворяет (**).Однопроходные решения могут в конечном итоге иметь смещенные распределения.

0 голосов
/ 15 ноября 2011

Обновление : Да, вы правы, результат распределен неравномерно.

Допустим, ваши процентные значения являются натуральными числами (если это предположение неверно, вы недолжен читать дальше :) В этом случае у меня нет решения).

Давайте определим событие e как кортеж из 3 значений (процент от каждого сегмента): e = (p a , p b , p c ).Далее создайте все возможные события e n .Здесь у вас есть кортеж, состоящий из дискретного числа событий.Все возможные события должны иметь одинаковую возможность происходить.

Допустим, у нас есть функция f (n) => e n .Затем все, что нам нужно сделать, это взять случайное число n и вернуть e n за один проход.

Теперь остается проблема создания такой функции f:)

В псевдокоде очень медленный метод (только для иллюстрации): 

function f(n) {
    int c = 0
    for i in [10..70] {
        for j in [10..50] {
            for k in [5..25] {
                if(i + j + k == 100) {
                    if(n == c) {
                        return (i, j, k) // found event!
                    } else {
                        c = c + 1
                    }
                }
            }
        }
    }
}

То, что вы знаете, - это однопроходное решение, но проблема только удалена.Функция f очень медленная.Но вы можете сделать лучше: я думаю, что вы можете вычислить все немного быстрее, если вы правильно установите свои диапазоны и вычислите смещения вместо итерации по вашим диапазонам.

Достаточно ли ясно это?* Прежде всего вам, вероятно, придется скорректировать свои диапазоны.10% в ведре a невозможно, поскольку вы не можете удержать условие a+b+c = number.

По вашему вопросу: (1) Выберите случайное число для ведра a в вашем диапазоне,затем (2) обновите диапазон для сегмента b с минимальным и максимальным процентом (вам следует только сузить диапазон).Затем (3) выберите случайное число для ведра b.В конце c следует рассчитать, что ваше условие выполнено (4).

Пример: 

    n = 1000
(1) a = 40%
(2) range b [35,50], because 40+35+25 = 100%
(3) b = 45%
(4) c = 100-40-45 = 15%

Или: 

    n = 1000
(1) a = 70%
(2) range b [10,25], because 70+25+5 = 100%
(3) b = 20%
(4) c = 100-70-20 = 10%

Это проверить,все события распределены равномерно.Если это должно быть проблемой, вы можете рандомизировать обновление диапазона в шаге 2.

...