在少量元素中分配大值

Question

我需要budget在一个带有n元素的小数组中随机分布一个大整数,这样数组中的所有元素都将具有相同的分布并总结,budget并且数组中的每个元素至少得到min.

我有一个在O(预算)中运行的算法:

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)运行甚至更好的算法？

Answer 1

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

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

如果您需要使用整数，您可以通过使用实值k和舍入来解决问题k*x[i]。然后，您必须跟踪累积舍入误差，并在计算值达到整个单位时添加或减去累积误差。您还必须将剩余值分配给最后一个元素才能达到 full 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;
}