我需要生成n个百分比（0到100之间的整数），使得这n个数字的和等于100。
如果我只是简单地使用nextInt() n次，并且每次都确保参数是100减去先前累加的总和，那么我的百分比就会有偏差（即最初生成的数字通常会更大等）。如何以无偏差的方式完成这个任务？
Java随机百分比
19
- erw
8
有趣的问题，但我认为答案不会特别涉及Java。 - Joachim Sauer
2你可以随机生成数字，直到它们的总和超过100，然后将最终的数字“限制”在100以内。这样除了最后一个数字之外，所有数字都是随机的。我不明白如何通过非随机约束来“随机”得出预设的总和。 - Alex
将它们的顺序随机化。 假设您有5个数字，那么您可能首先做#3，然后下一次是#4，接下来是#1等... - Romain Hippeau
2我认为在考虑这些随机数的分布情况之前，无法回答这个问题。如果你想要一个“正态分布”（钟形曲线），那么@LanceH的答案应该是可行的。如果你期望一个“均匀分布”，我怀疑这是不可能的。你想要的分布完全决定了解决方案的性质。 - Kevin Bourrillion
2@Kevin。如果人们忽略了概率分布，我会说假设均匀分布是合理的。而且，获得均匀分布是完全可能的，为什么你说不可能呢？ - Aryabhatta
显示剩余3条评论
12个回答
12
有人建议选择随机百分数并计算它们之间的差异。正如 Nikita Ryback 所指出的那样，这不会给出所有可能性的均匀分布；特别是，零会比预期的少。
为了解决这个问题，考虑从100个“百分比”开始并插入分隔符。我将以10个为例：
% % % % % % % % % %
总共有11个地方可以插入分隔符：在任意两个百分比之间或在开头或结尾。因此插入一个：
% % % % / % % % % % %
这表示选择了四个和六个。现在插入另一个分隔符。这一次，有12个位置，因为已经插入的分隔符创建了额外的位置。特别地，有两种方法可以得到
% % % % / / % % % % % %
可以在前一个分隔符之前或之后插入。您可以继续该过程，直到有所需数量的分隔符（比百分号少一个）。
% % / % / % / / % % % / % % % /
这对应于2、1、1、0、3、3、0。
我们可以证明这会给出均匀的分布。将100分成k部分的组合数是二项式系数100+k-1 choose 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)!种序列可以得到给定的组合。因此，任何特定组合的概率正好是应该的。
在实际代码中，您可能不会像这样表示您的步骤。您应该能够仅保留数字，而不是百分比和分隔符序列。我没有考虑这个算法的复杂性。
为了解决这个问题，考虑从100个“百分比”开始并插入分隔符。我将以10个为例：
% % % % % % % % % %
总共有11个地方可以插入分隔符：在任意两个百分比之间或在开头或结尾。因此插入一个：
% % % % / % % % % % %
这表示选择了四个和六个。现在插入另一个分隔符。这一次，有12个位置，因为已经插入的分隔符创建了额外的位置。特别地，有两种方法可以得到
% % % % / / % % % % % %
可以在前一个分隔符之前或之后插入。您可以继续该过程，直到有所需数量的分隔符（比百分号少一个）。
% % / % / % / / % % % / % % % /
这对应于2、1、1、0、3、3、0。
我们可以证明这会给出均匀的分布。将100分成k部分的组合数是二项式系数100+k-1 choose 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)!种序列可以得到给定的组合。因此，任何特定组合的概率正好是应该的。
在实际代码中，您可能不会像这样表示您的步骤。您应该能够仅保留数字，而不是百分比和分隔符序列。我没有考虑这个算法的复杂性。
- eruonna
9
1这并不是因为在分隔符之前或之后选择空格的可能性存在。基本上，有两种方法可以选择已经抽取的数字。(如果该数字已被抽取n次，则为n+1。) - eruonna
哦，如果你的意思是从已经抽出的数字列表中选择或者从0-100中选择任何一个数字（不一定是新的），那么它们是相同的。你只需要确保给每个选择相同的概率即可。 - eruonna
是的，那就是正确的做法。 - starblue
对我来说，这件事有点可疑，尽管我不是很了解它。对于给定的结果，可能存在多个导致它的除数插入序列。当结果不包含零时，只有n!种方法可以得到该结果（对应于可以放置除数的不同顺序）。但是当存在零时，重复性比那还要多...或者并不是这样吗？组合数学太难了。 - Kevin Bourrillion
想一想，那是
O(n^2) - 哎呀！ - BlueRaja - Danny Pflughoeft显示剩余4条评论
7
生成任意范围的n个随机整数（称其为a[1]..a[n]）。将这些整数相加并称之为b。你的百分比将为[a[1]/b, ..., a[n]/b]。
编辑：好的点，将结果四舍五入以确保总和为100并不容易。一种方法是取1..n中x的a[x]/b的下限作为您的整数，然后随机分配剩余单位100-（整数之和）。我不确定这是否会引入任何偏差到结果中。
- ataylor
6
1唯一的问题是a [0] / b可能不是整数。 - Nikita Rybak
@Nikita：那又怎样？只需四舍五入，使得四舍五入后的总和等于100即可。 - Ben S
这似乎是一个不错的解决方案。如果比率不是整数，我是否可以随机选择其中一个数字，并将其与总和与100之间的差异相加？这似乎可以最小化分布偏差。 - erw
2@Ben 那种调整会使分布不那么均匀（有些组合比其他组合更常见）。但是如果“任何范围”足够大，我同意它非常接近。 - Nikita Rybak
1-1：抱歉，这是无用的，而且让它正确会使它变得不必要地复杂。我相信mikera的解决方案更好。 - Aryabhatta
完成此操作后，您将获得一堆浮点数，这些浮点数带有小数百分比，总和为1。再随机一次()，并根据每个数值获得该百分比的最后一个%点。因此，如果您有（33.3,33.3和33.4），则前两个将有30％的机会，而最后一个将有40％的机会获得该最后一个％点。 - LanceH
6
你可能需要定义一下“偏差”的真实含义 - 但是，如果你所关心的只是数字分布与其位置无关，则可以通过以“有偏差”的方式创建数字，然后随机化其位置来实现。
另一种“无偏差”的方法是创建 n-1 个随机百分比，对它们进行排序（称之为 x1，x2，x3...），然后将最终的百分比定义为：
这样，您将获得n个随机数，它们相加等于100。
另一种“无偏差”的方法是创建 n-1 个随机百分比，对它们进行排序（称之为 x1，x2，x3...），然后将最终的百分比定义为：
x1
x2 - x1
x3 - x2
...
100 - x(n-1)
这样，您将获得n个随机数，它们相加等于100。
- mikera
6
@erw：这个解决方案比当前排名第一的解决方案好多了（在投票数方面）！它甚至少调用了一个随机数，而且没有涉及任何舍入等操作。此外，我认为我们可以“证明”它以相同的概率生成每个组合。 - Aryabhatta
+1 与Adamski的解决方案相同，并且在处理零时存在相同的问题。但如果所有元素都> 0，则完美。 - Nikita Rybak
@Nikita：如果你认为这是生成n-1个数字的多重集合，那么它会给出一个无偏分布（我想，但没有尝试证明），因为我们需要的每个分布都恰好对应一个多重集合。我的关于少调用一个随机数的说法并不准确，因为逐个生成随机数来创建多重集合是不公平的，正如你所说。实际上，我相信如果n足够小，只需调用_一个_随机数即可完成此操作。请参见：https://dev59.com/L07Sa4cB1Zd3GeqP2VHv#3003253。 - Aryabhatta
补充之前的评论。由于100选50 < 2 ^ 128，所以我们只需要进行两次64位随机数调用就可以完成这个操作！（我假设n <= 100）。 - Aryabhatta
2@Moron 为什么我们要限制自己只使用一个随机调用呢？而我提到的问题（你在争论那个问题，对吧？）在于他没有正确生成多重集：生成(1,2)多重集有两种“路径”（从序列[1,2]和[2,1]），而生成(1,1)只有一种方式。因此，第一种情况的概率是第二种情况的两倍。 - Nikita Rybak
@Nikita：我完全同意。他没有正确生成多重集合。我的意思是，我们需要用于均匀分布的n-1个数字的多重集（而不是n-1个数字序列）可以使用_一个_随机数调用来生成解决方案。也许我应该把它作为答案添加进去！ - Aryabhatta
5
- dreeves
4
1不幸的是，维基百科的文章对于大多数读者来说有点难以理解。我需要简化一下。 :) - Kevin Bourrillion
@Kevin：第一个算法与ataylor的相同，第二个算法与mikera的相同（不幸的是，它存在Nikita提出的问题——在文章中提到了已知的问题，但他们没有具体说明）。eruonna的解决方案解决了这个问题——有趣的是维基百科还不知道这个解决方案 :) - BlueRaja - Danny Pflughoeft
@BlueRaja：关于ataylor的解决方案并非如此。你必须从指数分布中生成，然后进行归一化。 - dreeves
@BlueRaja：eruonna的解决方案与证明总集合数量为100+N-1选择N的（很棒！）想法相同。然而它使用了过多的随机数调用。想象一下要生成这样的数字一百万次。对于n<=100，类似的想法可以仅使用一个（或两个）随机数调用来给我们提供集合。我在我的答案中详细描述了这一点。 - Aryabhatta
3
关键是生成0到100之间的N个随机数，但是将这些数字用作“标记”，而不是要输出的最终序列。然后按升序迭代标记列表，计算每个百分比以输出为（当前标记 - 上一个标记）。
这比仅仅一个接一个地生成和输出每个数字会得到更加均匀的分布。
示例：
这比仅仅一个接一个地生成和输出每个数字会得到更加均匀的分布。
示例：
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
- Adamski
3
我怀疑分布将与ataylor或我的解决方案相同。然而，你的方法涉及插入到BST中，因此时间复杂度为O(NlogN)，而不是O(N)。另外，你需要添加最后一个条目以使总和达到100。 - Il-Bhima
+1，我喜欢这个想法。每个有效的分布都可以转化为一组（n-1）个标记，因此我们也可以生成标记。虽然代码看起来很困难，但我相信它可以变得更简单 :) - Nikita Rybak
它确实存在零的问题。在考虑顺序的情况下，将生成n！种标记（1、2、..、n-1），而仅在一种情况下将生成标记集（100, 100, .., 100）（导致分布100, 0, .., 0）。 - Nikita Rybak
3
创建一个数组。在该数组的每个部分中随机放置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]);
}
}
}
- LanceH
5
2你的 n == 2 的程序只有一种方式可以达到分布 (100, 0)：在每一步中 rnd.nextInt == 0。但是，有很多种方法可以达到 (50, 50)：从 50 和 100 中的二项式系数。并且这两个分布应该具有相等的概率。 - Nikita Rybak
rnd.nextInt(2)会产生0或1，看起来运行良好。我得到的结果是（46,54），（48,52），（56,44）等等... - LanceH
@LanceH 注意到你的例子都聚集在(50,50)附近。比如(100,0)这样的例子出现的概率要低得多。 - ataylor
1误读了Nikita写的内容。 是的，它趋向于中间，对n=2来说看起来特别糟糕。但是对于n=2，通过简单的第一个数字的简单随机和确定第二个数字的方法，解决方案是微不足道的。对于n=3，没有提到期望。如果分布在所有三个数字之间是相等的，那么单个桶的分布就不会从0到100均匀...这可能意味着n=2也是同样的情况。至少它意味着n=2与n> 2完全不同。没有提及期望分配。 - LanceH
这个回答完全正确，因为没有提到预期的分布。 - Kevin Bourrillion
2
要精确地说，这取决于您希望样本如何无偏。以下是一种大致的方法，可以大致给您一个好的结果。
最后一个可能会有偏差，但其余部分应该是均匀的。
当然，如果您想以更准确的方式执行此操作，则必须使用Gibbs采样或Metropolis hastings。
- 从0,..100生成n-1个整数，例如a[i]为i = 0到n-2。
- 让total成为这些数字的总和
- 计算b[i] = floor(100*a[i]/total) ，其中i = 0到n-2
- 设置b[n-1] = 100 - (b[0] + ... b[n-2])。
最后一个可能会有偏差，但其余部分应该是均匀的。
当然，如果您想以更准确的方式执行此操作，则必须使用Gibbs采样或Metropolis hastings。
- Il-Bhima
1
我认为这是正确的方法。如果您可以去除整数限制，就可以摆脱四舍五入可能导致的一些偏差，但生成100个数字然后进行归一化的整个过程似乎是可靠的。 - Grembo
0
这是我为正在创建的程序编写的一些代码。当我尝试解决这个确切的问题时，我发现了这个线程，希望这能帮助其他人。设计基于阅读@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;
}
- Declan
0
首先，显而易见的解决方案。
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]内生成随机点，直到其中一个适合圆形为止 :)
- Nikita Rybak
13
如果第一个随机数是99，第二个随机数是2，会怎么样？ - Joachim Sauer
@Adamski 你不相信随机的力量吗？ :) 重复执行“do .. until”1000次对于大多数n的值来说应该已经足够了。 - Nikita Rybak
1哈哈，这就相当于乱序排序算法。虽然算法是正确的，但需要大量迭代才能完成。我正在计算次数！希望你是开玩笑的 :) - Il-Bhima
@Adamski 好的，聪明鬼，我在我的帖子中提到了复杂性问题 :) - Nikita Rybak
对于两个数字，概率为1/100，因此仅针对两个数字，您需要进行100次迭代，而对于n = 3，则要大得多。我会说它至少是指数级的。 - Il-Bhima
显示剩余8条评论
0
假设你有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]
- Peter Lawrey
3
根据中心极限定理，当n_buckets趋近于无穷大时，它将倾向于围绕中心点（总数/2）形成正态分布。我认为OP想要的是让每种可能的组合等可能地出现（即在所有加起来为100的n个整数集合上进行均匀分布）。 - Il-Bhima
@LL-Bhima，每个桶被增加的机会是相等的，为什么你会怀疑其他不平均的分布呢？ - Peter Lawrey
@Kevin 结果并不完全一致，但是在最后一个例子中最低值和最高值之间的差异远小于1%。 - Peter Lawrey
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接