Мне нужно сгенерировать n процентов (целые числа от 0 до 100), так что сумма всех n чисел добавит до 100.
Если я просто выполняю nextInt() n раз, каждый раз, гарантируя, что этот параметр равен 100 минус ранее накопленная сумма, мои проценты смещены (т.е. первое сгенерированное число обычно будет наибольшим и т.д.). Как я могу сделать это беспристрастно?
Пара ответов предполагает выбор случайных процентов и принятие различий между ними. Как указывает Никита Рыбак, это не даст равномерного распределения по всем возможностям; в частности, нули будут менее частыми, чем ожидалось.
Чтобы исправить это, подумайте о старте с 100-процентными процентами и вставке разделителей. Я приведу пример с 10:
% % % % % % % % % %
Есть одиннадцать мест, в которые мы могли бы вставить разделитель: между любыми двумя процентами или в начале или в конце. Поэтому вставьте один:
% % % % / % % % % % %
Это означает выбор из четырех и шести. Теперь вставьте еще один разделитель. На этот раз есть двенадцать мест, потому что добавленный разделитель создает и дополнительный. В частности, есть два способа получить
% % % % / / % % % % % %
либо вставки до или после предыдущего разделителя. Вы можете продолжить процесс, пока у вас не будет столько разделителей, сколько вам нужно (на один меньше, чем количество процентов).
% % / % / % / / % % % / % % % /
Это соответствует 2,1,1,0,3,3,0.
Мы можем доказать, что это дает равномерное распределение. Количество составов 100 на k частей - это биномиальный коэффициент 100 + k-1, выбирающий k-1. То есть (100 + k-1) (100 + k-2)... 101/(k-1) (k-2) *... * 2 * 1 Таким образом, вероятность выбора какой-либо конкретной композиции является обратной. Когда мы вставляем разделители по одному, сначала мы выбираем из 101 позиции, затем 102, 103 и т.д., Пока не получим 100 + k-1. Таким образом, вероятность любой конкретной последовательности вставок равна 1/(100 + k-1) *... * 101. Сколько последовательностей вставки дает один и тот же состав? Конечная композиция содержит k-1 делителей. Они могли быть вставлены в любом порядке, так что есть (k-1)! последовательности, которые приводят к данной композиции. Таким образом, вероятность того, что какой-либо конкретный состав будет именно тем, чем он должен быть.
В фактическом коде вы, вероятно, не будете представлять свои шаги, подобные этому. Вы должны уметь просто удерживать цифры, а не последовательности процентов и разделителей. Я не думал о сложности этого алгоритма.
Сгенерируйте n случайных целых чисел с любым диапазоном (назовите их a[1].. a[n]). Суммируйте свои целые числа и назовите это b. Ваши проценты будут [a[1]/b, ..., a[n]/b].
Изменить: хорошие точки, округляя результаты до 100 точно не-тривалю. Один из подходов состоял бы в том, чтобы взять слово a[x]/b для x в 1..n в качестве ваших целых чисел, а затем распределить единицы остатка 100-(sum of integers) случайным образом. Я не уверен, приведет ли это к какой-либо ошибке в результате.
Возможно, вам нужно определить, что вы на самом деле подразумеваете под "предвзятым", но если все, о чем вы заботитесь, состоит в том, что распределение чисел не зависит от их положения, тогда вы можете просто создать числа "предвзятым" способом и затем рандомизируйте свои позиции.
Другим "беспристрастным" методом будет создание n-1 случайных процентов, сортировка (назовем этот x1 x2 x3...), а затем определите ваши конечные проценты:
x1
x2 - x1
x3 - x2
...
100 - x(n-1)
Таким образом вы получите n случайных чисел, которые добавят 100.
Эта проблема известна как единая выборка из симплекса, а Википедия дает два алгоритма:
http://en.wikipedia.org/wiki/Simplex#Random_sampling
См. также следующие вопросы:
Ключ должен генерировать N случайных чисел от 0 до 100, но использовать их как "маркеры", а не конечную последовательность чисел для вывода. Затем вы перебираете свой список маркеров в порядке возрастания, вычисляя каждый процент для вывода как (текущий маркер - предыдущий маркер).
Это даст гораздо более равномерное распределение, чем просто генерация и вывод каждого номера по одному за раз.
Пример
import java.util.Random;
import java.util.TreeSet;
import java.util.SortedSet;
public class Main {
public static void main(String[] args) {
Random rnd = new Random();
SortedSet<Integer> set = new TreeSet<Integer>();
for (int i=0; i<9; ++i) {
set.add(rnd.nextInt(101));
}
if (set.last() < 100) {
set.add(100);
}
int prev = 0;
int total = 0;
int output;
for (int j : set) {
output = j - prev;
total += output;
System.err.println(String.format("Value: %d, Output: %d, Total So Far: %d", j, output, total));
prev = j;
}
}
}
Выход
$ java Main
Value: 0, Output: 0, Total So Far: 0
Value: 2, Output: 2, Total So Far: 2
Value: 55, Output: 53, Total So Far: 55
Value: 56, Output: 1, Total So Far: 56
Value: 57, Output: 1, Total So Far: 57
Value: 69, Output: 12, Total So Far: 69
Value: 71, Output: 2, Total So Far: 71
Value: 80, Output: 9, Total So Far: 80
Value: 92, Output: 12, Total So Far: 92
Value: 100, Output: 8, Total So Far: 100
Сделайте массив. Случайно уменьшайте 100% на каждую часть этого массива. Пример показывает n = 7.
import java.util.Random;
public class random100 {
public static void main (String [] args) {
Random rnd = new Random();
int percents[] = new int[7];
for (int i = 0; i < 100; i++) {
int bucket = rnd.nextInt(7);
percents[bucket] = percents[bucket] + 1;
}
for (int i = 0; i < 7; i++) {
System.out.println("bucket " + i + ": " + percents[i]);
}
}
}
Чтобы быть точным, это зависит от того, как вы хотите, чтобы образцы были объективными. Вот грубый способ, который грубо даст вам хороший результат.
n-1 целые числа от 0,.. 100, скажем a[i] для i = 0, to n-2.total - сумма этих чиселb[i] = floor(100*a[i]/total) для i = 0, to n-2b[n-1] = 100 - (b[0] + ... b[n-2]).Затем b - ваш итоговый массив процентов.
Последний будет смещен, но остальное должно быть равномерным.
Конечно, если вы хотите сделать это более точно, вам придется использовать выборку Gibbs или гастроли Metropolis.
Как только вы выбираете числа с помощью метода, который вы описываете, перетасовывайте порядок чисел. Таким образом, окончательный список чисел имеет более равномерное распределение.
Тем не менее, обратите внимание, что независимо от того, что вы делаете, вы не можете получить абсолютно равномерное распределение, так как после того, как вы начнете выбирать числа, ваши случайные испытания не являются независимыми. См. ответ ataylor.
Обратите также внимание, что описанный вами алгоритм может не дать вам требуемый результат. Последнее число не может быть случайным, так как оно должно сделать сумму равной 100.
Во-первых, очевидное решение.
do
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = random number between 0 and 100;
}
until sum(a) == 100;
Он не идеален с точки зрения сложности (количество итераций для достижения суммы 100 может быть довольно большим), но распределение, безусловно, "беспристрастно".
изменить
Аналогичная проблема: как создать случайную точку в круге с радиусом 1 и центром в (0, 0)? Решение: продолжайте генерировать случайные точки в диапазоне (квадрат) [-1.1, -1.1], пока один из них не будет соответствовать кругу:)
У меня была аналогичная проблема, и я закончил работу, как вы сказали, генерируя случайные целые числа до разницы суммы существующих целых чисел и лимита. Затем я рандомизировал порядок целых чисел. Он работал очень хорошо. Это было сделано для генетического алгоритма.
Представьте, что у вас есть 100 камней и N ведер, чтобы разместить их. Вы можете взять все 100 и поместить в случайное ведро. Таким образом, общее количество будет 100, с которого вы начали, и не будет никакого смещения между любым ведром.
public static int[] randomBuckets(int total, int n_buckets) {
int[] buckets = new int[n_buckets];
Random rand = new Random();
for(int i=0;i<total;i++)
buckets[rand.nextInt(n_buckets)]++;
return buckets;
}
public static void main(String... args) {
for(int i=2; i<=10;i++)
System.out.println(Arrays.toString(randomBuckets(100, i)));
}
Печать
[55, 45]
[38, 34, 28]
[22, 21, 32, 25]
[28, 24, 18, 15, 15]
[17, 14, 13, 21, 18, 17]
[17, 19, 14, 15, 6, 15, 14]
[11, 14, 14, 14, 4, 17, 9, 17]
[13, 12, 15, 12, 8, 10, 9, 11, 10]
[11, 13, 12, 6, 6, 11, 13, 3, 15, 10]
По мере того, как счет увеличивается, распределение приближается к равномерному.
System.out.println(Arrays.toString(randomBuckets(100000000, 100)));
Печать
[1000076, 1000612, 999600, 999480, 998226, 998303, 1000528, 1000450, 999529,
998480, 998903, 1002685, 999230, 1000631, 1001171, 997757, 1000349, 1000527,
1002408, 1000852, 1000450, 999318, 999453, 1000099, 1000759, 1000426, 999404,
1000758, 1000939, 999950, 1000493, 1001396, 1001007, 999258, 1001709, 1000593,
1000614, 1000667, 1000168, 999448, 999350, 1000479, 999991, 999778, 1000513,
998812, 1001295, 999314, 1000738, 1000211, 999855, 999349, 999842, 999635,
999301, 1001707, 998224, 1000577, 999405, 998760, 1000036, 1000110, 1002471,
1000234, 1000975, 998688, 999434, 999660, 1001741, 999834, 998855, 1001009,
999523, 1000207, 998885, 999598, 998375, 1000319, 1000660, 1001727, 1000546,
1000438, 999815, 998121, 1001128, 1000191, 998609, 998535, 999617, 1001895,
999230, 998968, 999844, 999392, 999669, 999407, 998380, 1000732, 998778, 1000522]
Вот код, который я написал для программы, которую я создаю. Я нашел эту тему, пытаясь решить эту точную проблему, поэтому, надеюсь, это поможет некоторым другим. Дизайн был основан на чтении ответа @eruonna выше.
public static int[] randomNumbers(int numOfNumbers){
int percentN = numOfNumbers;
int[] intArray = new int[101];
//set up the array with values
for(int i = 0; i < intArray.length; i++){
intArray[i] = i;
}
//set up an array to hold the selected values
int[] selectionArray = new int[(percentN - 1)];
//run a for loop to go through and select random numbers from the intArray
for(int n = 0; n < selectionArray.length; n++){
int randomNum = (int)(Math.random() * 100);
selectionArray[n] = intArray[randomNum];
}
//bubble sort the items in the selectionArray
for(int out = (selectionArray.length - 1); out > 1; out--){
for(int in = 0; in < out; in++){
if(selectionArray[in] > selectionArray[in + 1]){
int temp = selectionArray[in];
selectionArray[in] = selectionArray[in + 1];
selectionArray[in + 1] = temp;
}
}
}
//create an array to hold the calculated differences between each of the values to create random numbers
int[] calculationArray = new int[percentN];
//calculate the difference between the first item in the array and 0
calculationArray[0] = (selectionArray[0] - 0);
//calculate the difference between the other items in the array (except for the last value)
for(int z = 1; z < (calculationArray.length - 1); z++){
calculationArray[z] = (selectionArray[z] - selectionArray[z - 1]);
}
//calculate the difference for the last item in the array
calculationArray[(calculationArray.length - 1)] = (100 - selectionArray[(selectionArray.length - 1)]);
return calculationArray;
}