试图实现一个简单的算法

Question

我有N个选项,介于1到数千之间.例如,我将用3个选项解释它,但是我需要这个算法来处理N个选项.

• A = 30%的可能性
• B = 50%的可能性
• C = 20%的可能性

我需要随机获得这三个选项之一,但根据概率.

我通过生成0到100之间的随机数来实现它,并且我正在做一些沉重和丑陋的代码来知道数字在0和A可能性数字之间,A可能性和B可能性之间等等.

你知道更好的方法吗？

Answer 1

选择您需要的范围内的随机数,开始从该数字中减去每个选项的概率,直到达到0.您减去的最后概率是您想要的.

int[] possibilities = new int[] {20,50,30};
Random rand = new Random();
int r = rand.nextInt(100);
int i = 0;
for (i=0;i<possibilities.length; i++) {
  r -= possibilities[i];
  if (r <= 0)
    break;
}
System.out.println(i); // the index of the possibility

Answer 2

即使给出了大量不同的选项(假设您不止一次从同一组选项中选择),其中一种方法是执行此操作,即构建一个累积概率表,然后对它们进行二进制搜索.

也就是说,假设您有以下预期结果:[0.2,0.2,0.5,0.05,0.05]

我们通过使每个元素成为原始列表中所有前面元素的总和来构建一组累积概率:[0.0,0.2,0.4,0.9,0.95]

为了随机选择结果,我们生成一个介于0和1之间的随机数,并对列表进行二进制搜索,以找到小于它的最大索引.这将选择每个元素与它与前一个元素之间的间隙成比例,这是原始概率的数量.