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#Random_sampling

См. Также следующие вопросы:

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

Answer 5

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

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

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

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

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

Answer 8

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

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

Answer 10

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