java случайные проценты

Question

Мне нужно сгенерировать n процентов (целых чисел от 0 до 100), чтобы сумма всех n чисел складывалась до 100.

Если я просто сделаю nextInt() n раз, каждый раз гарантируя, что параметр равен 100 минус ранее накопленная сумма, тогда мои проценты смещены (т.е. первое сгенерированное число обычно будет наибольшим и т. д.). Как мне сделать это непредвзято?

Answer 1

Пара ответов предлагает выбрать случайные проценты и взять разницу между ними. Как указывает Никита Райбек, это не даст равномерного распределения по всем возможностям; в частности, нули будут менее частыми, чем ожидалось.

Чтобы это исправить, подумайте о том, чтобы начать со 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. Сколько последовательностей вставки дают один и тот же состав? Конечная композиция содержит к-1 делители. Они могли быть вставлены в любом порядке, поэтому есть (k-1)! последовательности, которые дают начало данной композиции. Таким образом, вероятность того или иного конкретного состава именно то, что и должно быть.

В реальном коде вы, вероятно, не представляете свои шаги таким образом. Вы должны быть в состоянии просто удерживать цифры, а не последовательности процентов и делителей. Я не думал о сложности этого алгоритма.

Answer 2

Генерация n случайных чисел с любым диапазоном (назовите их a[1]..a[n]). Подведите ваши целые числа и назовите это b, Ваши проценты будут [a[1]/b, ..., a[n]/b],

Изменить: хорошие моменты, округление результатов до 100 точно не тривиально. Одним из подходов было бы взять слово a[x]/b за x в 1..n как ваши целые числа, а затем распределить оставшиеся единицы 100-(sum of integers) случайным образом. Я не уверен, что это внесет какой-либо уклон в результат.

Answer 3

Возможно, вам нужно определить, что вы на самом деле подразумеваете под "предвзятым" - но если все, что вас волнует, это то, что распределение чисел не зависит от их положения, то вы можете просто создать числа "предвзятым" способом и затем рандомизировать их позиции.

Другой "непредвзятый" метод будет состоять в том, чтобы создать n-1 случайный процент, отсортировать его (назовите это x1 x2 x3...) и затем определить ваш окончательный процент:

x1
x2 - x1
x3 - x2
...
100 - x(n-1)

Таким образом, вы получите n случайных чисел, которые добавляются к 100.

Answer 4

Эта проблема известна как равномерная выборка из симплекса, и в Википедии есть два алгоритма:

http://en.wikipedia.org/wiki/Simplex

Смотрите также эти связанные вопросы:

• Равномерная выборка случайным образом из n-мерного единичного симплекса
• Генерация вероятностного распределения

Answer 5

Ключ должен генерировать 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

Answer 6

Сделай массив. Случайно бросьте 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]);
        }

    }

}

Answer 7

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

1. генерировать n-1 целые числа от 0,..100, скажем a[i] за i = 0, to n-2,
2. Позволять total быть суммой этих чисел
3. вычисление b[i] = floor(100*a[i]/total) за i = 0, to n-2
4. Задавать b[n-1] = 100 - (b[0] + ... b[n-2]),

Тогда б ваш результирующий массив процентов.

Последний будет предвзятым, а остальные должны быть единообразными.

Конечно, если вы хотите сделать это более точно, вам придется использовать выборку Гиббса или Гастингс из Метрополиса.

Answer 8

Во-первых, очевидное решение.

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], пока одна из них не окажется в круге:)

Answer 9

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

Answer 10

После того, как вы выберете числа с помощью описанного вами метода, перетасуйте порядок чисел. Таким образом, окончательный список чисел имеет более равномерное распределение.

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

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

Answer 11

Вот код, который я написал для программы, которую я создаю. Я нашел эту ветку, когда пытался решить именно эту проблему, так что, надеюсь, это поможет некоторым другим. Дизайн был основан на прочтении ответа @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;

}

Answer 12

Представьте, что у вас есть 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]