例如:
生成介于[1;3]之间的随机整数,并具有以下概率:
P(1)= 0.2
P(2)= 0.3
P(3)= 0.5
目前我正在考虑的方法是在[0;100]内生成随机整数,并执行以下操作:
如果它在[0;20]之间 - 我得到了我的随机数字1。
如果它在[21;50]之间 - 我得到了我的随机数字2。
如果它在[51;100]之间 - 我得到了我的随机数字3。
你认为呢?
你已经有一个相当不错的方法,可以在任何范围内很好地工作。
仅仅思考一下:另一个可能性是通过乘以一个常数乘子来消除分数,然后构建一个具有这个乘子的大小的数组。 乘以10,你就得到
P(1) = 2
P(2) = 3
P(3) = 5
然后您可以创建一个反向值的数组——'1'放入元素1和2中,'2'放入3到6中,以此类推:
P = (1,1, 2,2,2, 3,3,3,3,3);
然后您可以从这个数组中随机选择一个元素。
(附加.) 使用kiruwka评论中的示例中的概率:
int[] numsToGenerate = new int[] { 1, 2, 3, 4, 5 };
double[] discreteProbabilities = new double[] { 0.1, 0.25, 0.3, 0.25, 0.1 };
使所有数字变为整数的最小乘数是20,这将给你
2, 5, 6, 5, 2
所以numsToGenerate
的长度将为20,具有以下值:
1 1
2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4
5 5
分布完全相同:例如数字 '1' 的概率现在是20次中出现2次——仍为0.1。
这基于您原始的概率总和为1。如果不是,请将总数乘以相同的因子(这将成为您的数组长度)。
前些时候我编写了一个助手类来解决这个问题。源代码应该足够清晰地展示概念:
public class DistributedRandomNumberGenerator {
private Map<Integer, Double> distribution;
private double distSum;
public DistributedRandomNumberGenerator() {
distribution = new HashMap<>();
}
public void addNumber(int value, double distribution) {
if (this.distribution.get(value) != null) {
distSum -= this.distribution.get(value);
}
this.distribution.put(value, distribution);
distSum += distribution;
}
public int getDistributedRandomNumber() {
double rand = Math.random();
double ratio = 1.0f / distSum;
double tempDist = 0;
for (Integer i : distribution.keySet()) {
tempDist += distribution.get(i);
if (rand / ratio <= tempDist) {
return i;
}
}
return 0;
}
}
该类的使用方法如下:
DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator();
drng.addNumber(1, 0.3d); // Adds the numerical value 1 with a probability of 0.3 (30%)
// [...] Add more values
int random = drng.getDistributedRandomNumber(); // Generate a random number
测试驱动程序以验证功能:
public static void main(String[] args) {
DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator();
drng.addNumber(1, 0.2d);
drng.addNumber(2, 0.3d);
drng.addNumber(3, 0.5d);
int testCount = 1000000;
HashMap<Integer, Double> test = new HashMap<>();
for (int i = 0; i < testCount; i++) {
int random = drng.getDistributedRandomNumber();
test.put(random, (test.get(random) == null) ? (1d / testCount) : test.get(random) + 1d / testCount);
}
System.out.println(test.toString());
}
这个测试驱动程序的示例输出:
{1=0.20019100000017953, 2=0.2999349999988933, 3=0.4998739999935438}
Float
而不是 Double
,以减少不必要的开销。 - xerufmain()
函数中的 for 循环?我不明白它在做什么。另外,在进行计算之前,为什么不检查 distSum
是否为 1
? - user366312if (this.distribution.get(value) != null) { distSum -= this.distribution.get(value); }
? - user366312addNumber(int value,...)
,则此行确保总和distSum
保持正确的值。 - trylimitstest.put(random, (test.get(random) == null) ? (1d / testCount) : test.get(random) + 1d / testCount);
?1d / testCount
的作用是什么?您能否解释一下这段代码的逻辑,如果我想搜索它的名称(例如反向累积分布等),该怎么办?我不明白它是如何完成工作的。 - noobie(1d / testCount)
用于计算测试驱动程序的平均值。另一种可能更易理解的方法是计算每个随机数并将其除以 testcount
。
我不知道这个算法是否有专门的名称。我实现了这个类来将其用作 轮盘赌选择 - 可能这就是你要找的名称。 - trylimits你已经在你的问题中写出了实现方式。 ;)
final int ran = myRandom.nextInt(100);
if (ran > 50) { return 3; }
else if (ran > 20) { return 2; }
else { return 1; }
t[0] = 1; t[1] = 1; // ... one for each possible result
return t[ran];
但是只有在这是性能瓶颈并且每秒被调用数百次时才应该使用此方法。
如果您遇到性能问题,而不是搜索所有n个值 O(n),
您可以进行二进制搜索,其成本为O(log n)
Random r=new Random();
double[] weights=new double[]{0.1,0.1+0.2,0.1+0.2+0.5};
// end of init
double random=r.nextDouble();
// next perform the binary search in weights array
如果您有很多权重元素,平均只需要访问log2(weights.length)。
1/e
或1/PI
)的结果。O(n)
的工作来设置n
个结果的表,但无论结果有多少,生成时间都是恒定的。 List<Character> charset = Arrays.asList('A','B','C','D','E','F','G','H','I','J');
List<Integer> weight = Arrays.asList(10,30,25,60,20,70,10,80,20,30);
List<Integer> weightsum = new ArrayList<>();
int i=0,j=0,k=0;
Random Rnd = new Random();
weightsum.add(weight.get(0));
for (i = 1; i < 10; i++)
weightsum.add(weightsum.get(i-1) + weight.get(i));
for (j = 0; j < 30; j++)
{
Random r = new Random();
k = r.nextInt(weightsum.get(weightsum.size()-1));
for (i = 0; k > weightsum.get(i); i++) ;
System.out.print(charset.get(i));
}
这段代码输出以下字符序列:
HHFAIIDFBDDDHFICJHACCDFJBGBHHB
让我们来算一下!
A = 2
B = 4
C = 3
D = 5
E = 0
F = 4
G = 1
H = 6
I = 3
J = 2
总计:30
按照我们的要求,D和H出现的概率更高(分别为70%和80%)
否则E根本没有出现。(10%的概率)
除了涉及分数、创建大型数组或硬编码范围到100之外,还有一种更有效的方法。
在您的情况下,数组变为int[]{2,3,5},总和为10,只需将所有概率的总和运行随机数生成器,结果=New Random().nextInt(10)
从索引0开始迭代数组元素,并计算总和,当总和大于返回该索引的元素时,将其作为输出返回。
例如,如果结果为6,则将返回索引2,即5。
此解决方案可以扩展,无论具有大数字或范围大小。
参考 pjs 在另一个帖子中提到的论文,base64表的数量可以进一步优化。结果非常快,初始化稍微有点贵,但如果概率不经常改变,这是一个好方法。
*对于重复键,取最后一个概率而不是组合(与EnumeratedIntegerDistribution行为略有不同)
public class RandomGen5 extends BaseRandomGen {
private int[] t_array = new int[4];
private int sumOfNumerator;
private final static int DENOM = (int) Math.pow(2, 24);
private static final int[] bitCount = new int[] {18, 12, 6, 0};
private static final int[] cumPow64 = new int[] {
(int) ( Math.pow( 64, 3 ) + Math.pow( 64, 2 ) + Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),
(int) ( Math.pow( 64, 2 ) + Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),
(int) ( Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),
(int) ( Math.pow( 64, 0 ) )
};
ArrayList[] base64Table = {new ArrayList<Integer>()
, new ArrayList<Integer>()
, new ArrayList<Integer>()
, new ArrayList<Integer>()};
public int nextNum() {
int rand = (int) (randGen.nextFloat() * sumOfNumerator);
for ( int x = 0 ; x < 4 ; x ++ ) {
if (rand < t_array[x])
return x == 0 ? (int) base64Table[x].get(rand >> bitCount[x])
: (int) base64Table[x].get( ( rand - t_array[x-1] ) >> bitCount[x]) ;
}
return 0;
}
public void setIntProbList( int[] intList, float[] probList ) {
Map<Integer, Float> map = normalizeMap( intList, probList );
populateBase64Table( map );
}
private void clearBase64Table() {
for ( int x = 0 ; x < 4 ; x++ ) {
base64Table[x].clear();
}
}
private void populateBase64Table( Map<Integer, Float> intProbMap ) {
int startPow, decodedFreq, table_index;
float rem;
clearBase64Table();
for ( Map.Entry<Integer, Float> numObj : intProbMap.entrySet() ) {
rem = numObj.getValue();
table_index = 3;
for ( int x = 0 ; x < 4 ; x++ ) {
decodedFreq = (int) (rem % 64);
rem /= 64;
for ( int y = 0 ; y < decodedFreq ; y ++ ) {
base64Table[table_index].add( numObj.getKey() );
}
table_index--;
}
}
startPow = 3;
for ( int x = 0 ; x < 4 ; x++ ) {
t_array[x] = x == 0 ? (int) ( Math.pow( 64, startPow-- ) * base64Table[x].size() )
: ( (int) ( ( Math.pow( 64, startPow-- ) * base64Table[x].size() ) + t_array[x-1] ) );
}
}
private Map<Integer, Float> normalizeMap( int[] intList, float[] probList ) {
Map<Integer, Float> tmpMap = new HashMap<>();
Float mappedFloat;
int numerator;
float normalizedProb, distSum = 0;
//Remove duplicates, and calculate the sum of non-repeated keys
for ( int x = 0 ; x < probList.length ; x++ ) {
mappedFloat = tmpMap.get( intList[x] );
if ( mappedFloat != null ) {
distSum -= mappedFloat;
} else {
distSum += probList[x];
}
tmpMap.put( intList[x], probList[x] );
}
//Normalise the map to key -> corresponding numerator by multiplying with 2^24
sumOfNumerator = 0;
for ( Map.Entry<Integer, Float> intProb : tmpMap.entrySet() ) {
normalizedProb = intProb.getValue() / distSum;
numerator = (int) ( normalizedProb * DENOM );
intProb.setValue( (float) numerator );
sumOfNumerator += numerator;
}
return tmpMap;
}
}
如果您不反对在代码中添加新库,此功能已经在MockNeat中实现,请查看probabilities()方法。
以下是一些来自维基的示例:
String s = mockNeat.probabilites(String.class)
.add(0.1, "A") // 10% chance
.add(0.2, "B") // 20% chance
.add(0.5, "C") // 50% chance
.add(0.2, "D") // 20% chance
.val();
或者,如果您想要在给定范围内以给定概率生成数字,可以执行以下操作:
Integer x = m.probabilites(Integer.class)
.add(0.2, m.ints().range(0, 100))
.add(0.5, m.ints().range(100, 200))
.add(0.3, m.ints().range(200, 300))
.val();
免责声明:本库的作者是我,因此在推荐时可能存在偏见。
这里也有回应:找到随机国家,但选择人口更高的国家的概率应该更高。使用TreeMap:
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(percent1, 1);
map.put(percent1 + percent2, 2);
// ...
int random = (new Random()).nextInt(100);
int result = map.ceilingEntry(random).getValue();