根据帕累托原则从列表中随机选择

Question

我有一个 List<T> 并尝试根据 Pareto Principle 随机挑选物品，所以前 20% 的物品将被挑选 80% 次，其余 80% 的物品将被挑选 20% 次.到目前为止，我有一个简单的实现：

static <T> T pickPareto(List<T> list) {
    int n = list.size();
    int first = n * 0.2;
    return rnd.nextFloat() < 0.8            
           ? list.get(rnd.nextInt(first))                // pick one of first 20%
           : list.get(first + rnd.nextInt(n - first));   // pick one of remaining 80%
}

它运行良好，但根据 阶梯函数.

的分布挑选项目

有谁知道如何根据 平滑函数 的分布 select 项目（可能不完全是 Pareto，但保持 20/80 属性）？

Answer 1

使用nextFloat()，它会根据这个随机数生成器的序列为您提供下一个伪随机、均匀分布的浮点值，该值介于 0.0 和 1.0 之间。

return rnd.nextFloat() < 0.8            
       ? list.get(rnd.nextInt(first))                // pick one of first 20%
       : list.get(first + rnd.nextInt(n - first));   // pick one of remaining 80%

此外，我假设 rnd 是浮动的。

Answer 2

经过一段时间的研究，我发现这个问题可以简化为求函数的问题，将其应用于产生均匀随机分布的函数（例如.nextFloat()），得到期望的分布.

这样的函数f(x)必须满足以下所有条件:

f(0) = 0
f(x) → 1 对于 x → 1
在区间 [0, 1)
区间平滑 [0, 1)
f(0.8) = 0.2 -- 80/20 帕累托原则的条件，或者，一般来说，f(p) = 1 - p

终于，我成功实现了这样的功能。它可以是：

f(x) = (x^a + 1 – (1 – x)^1/a) / 2,
a = log_p(1 – p)

此处参数 p ∈ (0, 1) 的含义与条件 5 中的含义完全相同：它是一个调整参数，显示结果分布与均匀分布有何不同。例如，如果 p = 0.8 则 f(0.8) = 0.2。如果 p = 0.5，则 a = 1，因此函数将折叠为 f(x) = x。

p = 0.8 的图表：

所以从列表中选择的方法如下所示：

public static <T> T pickRandomly(List<T> list, float p) {
    if (p <= 0 || p >= 1.0)
        throw new IllegalArgumentException();
    double a = Math.log(1.0 - p) / Math.log(p);
    double x = rnd.nextDouble();
    double y = (Math.pow(x, a) + 1.0 - Math.pow(1.0 - x, 1.0 / a)) / 2.0;
    return list.get((int) (list.size() * y));
}

例如，从 10 个整数的列表中选取 1000 次，p = 0.8:

0: 646
1: 153  // 0 or 1 occured 799 times
2: 60
3: 57
4: 32
5: 26
6: 18
7: 7
8: 1
9: 0

根据帕累托原则从列表中随机选择

Picking from list randomly according to Pareto Principle

java

random

distribution