5

我需要budget在一个带有元素的小数组中随机分配一个大整数n，以便数组中的所有元素具有相同的分布并求和，budget并且数组中的每个元素至少得到min.

我有一个在 O(budget) 中运行的算法：

private int[] distribute(int budget, int n, int min) {
  int[] subBudgets = new int[n];
  for (int i = 0; i < n; i++) {
    subBudgets[i] = min;
  }
  budget -= n * min;
  while (budget > 0) {
    subBudgets[random.nextInt(n)]++;
    budget--;
  }
  return subBudgets;
}

但是，当budget增加时，它可能非常昂贵。有没有运行在 O(n) 甚至更好的算法？

4

4 回答 4

4

首先生成n随机数x[i]，将它们相加，然后除以总budget和，您将得到k。然后分配k*x[i]给每个数组元素。它很简单而且 O(n)。

如果您希望每个元素中至少有min值，您可以通过min（或使用）填充所有元素并在开始上述算法之前k*x[i] + min分包n*min来修改上述算法。budget

如果您需要使用整数，您可以使用 real valuek和 rounding来解决问题k*x[i]。然后，您必须跟踪累积舍入误差，如果计算值达到整个单位，则从计算值中添加或减去累积误差。您还必须将剩余值分配给最后一个元素才能达到整体budget。

PS：请注意，此算法可以在纯函数式语言中轻松使用。这就是为什么我喜欢这一系列算法为每个成员生成随机数然后进行一些处理的原因。Erlang 中的实现示例：

-module(budget).

-export([distribute/2, distribute/3]).

distribute(Budget, N) ->
  distribute(Budget, N, 0).

distribute(Budget, N, Min) when
    is_integer(Budget), is_integer(N), N > 0,
    is_integer(Min), Min >= 0, Budget >= N*Min ->
  Xs = [random:uniform() || _ <- lists:seq(1,N) ],
  Rest = Budget - N*Min,
  K = Rest / lists:sum(Xs),
  F = fun(X, {Bgt, Err, Acc}) ->
      Y = X*K + Err,
      Z = round(Y),
      {Bgt - Z, Y - Z, [Z + Min | Acc]}
  end,
  {Bgt, _, T} = lists:foldl(F, {Rest, 0.0, []}, tl(Xs)),
  [Bgt + Min | T].

C ++中的相同算法（？？我不知道。）

private int[] distribute(int budget, int n, int min) {
  int[] subBudgets = new int[n];
  double[] rands = new double[n];
  double k, err = 0, sum = 0;
  budget -= n * min;
  for (int i = 0; i < n; i++) {
    rands[i] = random.nextDouble();
    sum += rands[i];
  }
  k = (double)budget/sum;
  for (int i = 1; i < n; i++) {
    double y = k*rands[i] + err;
    int z = floor(y+0.5);
    subBudgets[i] = min + z;
    budget -= z;
    err = y - z;
  }
  subBudgets[0] = min + budget;
  return subBudgets;
}
于 2013-10-22T22:59:18.243 回答
1

从多项分布中抽样

您当前将剩余的美元分配min给每个子预算的方式涉及执行固定数量budget的随机“试验”，在每次试验中，您随机选择一个n类别，并且您想知道每个类别的次数被选中。这是由具有以下参数的多项分布建模的：

  • 试验次数（n在 WP 页面上调用）：budget
  • 类别数（k在 WP 页面上调用）：n
  • i每个试验中的类别概率，对于1 <= i <= n：1/n

如果试验数量与类别数量大致相同或更少，那么您当前的做法是一个好方法。但如果预算很大，还有其他更有效的方法从这个分布中抽样。我所知道的最简单的方法是注意到具有k类别的多项分布可以通过将类别组合在一起来重复分解为二项分布：而不是直接将每个类别有多少选择k，我们将其表达为一系列问题： “如何在第一类和另一类之间分配预算k-1？” 我们接下来会问“如何在第二类和另一类之间分割剩余部分k-2？”等。

因此，顶级二项式具有类别（子预算）1 与其他所有项。通过从带有参数的二项式分布中抽取 1 个样本来确定进入子预算 1 的美元数量，n = budget并且p = 1/n（如何做到这一点在此处描述）；这将产生一些数字0 <= x[1] <= n。要找到进入子预算 2 的美元数量，请从剩余资金的二项式分布中抽取 1 个样本，即使用参数n = budget - x[1]和p = 1/(n-1)。在获得子预算 2 的金额 x[2] 后，将使用参数n = budget - x[1] - x[2]和找到子预算 3 p = 1/(n-2)，依此类推。

于 2013-10-22T22:47:25.047 回答
1

将@Hynek -Pichi- Vychodil 的想法和我的原始算法相结合，我提出了以下算法，该算法在 O(n) 中运行，并且所有舍入误差都均匀分布到数组中：

private int[] distribute(int budget, int n, int min) {
  int[] subBudgets = new int[n];
  for (int i = 0; i < n; i++) {
    subBudgets[i] = min;
  }
  budget -= n * min;
  if (budget > 3 * n) {
    double[] rands = new double[n];
    double sum = 0;
    for (int i = 0; i < n; i++) {
      rands[i] = random.nextDouble();
      sum += rands[i];
    }
    for (int i =0; i < n; i++) {
      double additionalBudget = budget / sum * rands[i];
      subBudgets[i] += additionalBudget;
      budget -= additionalBudget;
    }
  }
  while (budget > 0) {
    subBudgets[random.nextInt(n)]++;
    budget--;
  }
  return subBudgets;
}
于 2013-10-23T18:33:35.170 回答
0

让我用一个例子来演示我的算法：

认为budget = 100, n = 5, min = 10

将数组初始化为：

[10, 10, 10, 10, 10]=>current sum = 50

生成一个从0到50(50是budget - current sum) 的随机整数：

说随机整数是20并更新数组：

[30, 10, 10, 10, 10]=>current sum = 70

生成一个从0到30(30是budget - current sum) 的随机整数：

说随机整数是5并更新数组：

[30, 15, 10, 10, 10]=>current sum = 75

重复上面的过程，最后一个元素就是剩下的。

最后，打乱数组得到最终结果。

于 2013-10-22T23:23:23.280 回答