问从分布相等的数组中选择随机项

EN

如果您可以预先计算结果(即您需要有限的结果，而不是无限流)，并且结果的数量可以被项目数除以，那么您可以得到一个完美的分布：

1. 生成一个重复这些项的数组，直到得到足够多的项，即[1, 2, 3, 1, 2, 3, 1, 2, 3, ...]。因此，保证数组具有与每个项相同的实例。
2. 使用公平的洗牌算法(例如费舍-耶茨 )对数组进行洗牌。该数组仍然具有与每个项完全相同的实例。

如果您确实需要一个无限流，您可以使用类似于“项目包”模型(顺便说一句，这就是在俄罗斯方块的选择)：

1. 用你的物品填充一个“袋子”([1, 2, 3])。洗牌(如上)。
2. 当你需要一件物品时，把第一件东西从拖着的袋子里拿出来。
3. 如果袋子是空的，请按照步骤1重新填入。

唯一的情况，这没有一个完美的分布是，如果你停止“中袋”。

您在问题中所展示的只是这样一个事实: JavaScript随机数生成器不仅模拟均匀分布的随机数，而且模拟独立的随机数；每个选定的数字的行为似乎独立于任何其他选择。由于这种独立性，每个数字“不关心”每个数字被选择的频率，只要每个选择，每个可能的结果都与任何其他的结果一样(根据JavaScript生成器)。

如果您想要一个“感觉”更一致的分布，您将不得不调整每个结果的机会，以便机会取决于先前的结果。先前的一个答案说明了如何做到这一点。这是另一个，我给出了一个相似问题的答案。

1. 赋予每个项目相同的权重，指定为正整数。例如，每个项目的权重为20。
2. 使用加权选择和替换算法。也许最简单的是拒绝抽样，描述如下。假设最高的权重是max，并且每个权重都是0或更大。若要在间隔1中选择整数，请使用拒绝抽样进行weights.length：

1. Choose a uniform random integer `i` in [1, `weights.length`].
2. With probability `weights[i]/max`, return `i`. Otherwise, go to step 1.  (For example, if all the weights are integers greater than 0, choose a uniform random integer in [1, `max`] and if that number is `weights[i]` or less, return `i`, or go to step 1 otherwise.)

除了拒绝抽样之外，还有许多其他方法可以进行加权选择；参见我的关于加权选择算法的注记。

1. 当每个项目都被选中时，将其重量减少1，以减少被选择的可能性。
2. 如果所有权重都为0，则为每个项目分配步骤1中选择的相同权重(在本例中为20)。

你没有具体说明你想到的是哪种应用程序，但我看到这种“更均匀”分布的愿望经常出现在那些希望控制哪个随机数出现的游戏中，以使随机结果对玩家来说更“公平”。然而，在这种情况下，你也应该考虑是否应该做一个(普通的)独立的一致随机选择，特别是当你关心玩家是否可以通过预测随机结果获得不公平的优势时。

在这里，另一种方法--计数样本数已经发生，从范畴分布中选择值，但与计数的概率相反，因此更频繁的项目下一次采样的可能性较小。

一些代码(在C#中)

import MathNet.Numerics.Distributions;

static void Main() {

    const int N = 4;

    var counts  = new int [N] {1, 1, 1, 1};
    var weights = new double [N] {1.0, 1.0, 1.0, 1.0};

    while (true) {
        int v = Categorical.Sample(weights[k]); // sample one value in [0...N)
        // update counts and weights
        counts[v] += 1;
        weights[v] = 1.0/(double)counts[v];
        
        // use v here for something
        ...
    }
}

实际上，计数的任何单调增长函数都可以，f.e。

weights[v] = 1.0/(1.0 + .5*(double)counts[v]);

可能有用，或者

var squared => (x) => x*x;
weights[v] = 1.0/(7.0 + .25*squared((double)counts[v]));

或

weights[v] = 1.0/(3.0 + Math.Sqrt((double)counts[v]));