如何生成一个n个随机正整数序列,它们加起来有些价值？

Question

我正在尝试生成一个整数数组,其中包含与特定值相加的randoms.这是我的代码:

private long[] getRandoms(long size , long sum) throws Exception {
  double iniSum = 0;
  System.out.println("sum = " + sum);
  long[] ret = new long[(int) size];
  for (int i = 0 ; i < ret.length; i++) {
    ret[i] = randomInRange(1, sum);
    iniSum += ret[i];
  }

  double finSum = 0;
  for (int i = 0 ; i < ret.length; i++) {
    ret[i] =  Math.round((sum * ret[i]) / iniSum);
    System.out.println("ret[" + i +"] = " + ret[i]);
    finSum += ret[i];
  }

  if (finSum != sum) throw new Exception("Could not find " + size + " numbers adding up to " + sum  + " . Final sum = " + finSum);
  return ret;
}



private long randomInRange(long min , long max) {
  Random rand = new Random();
  long ret = rand.nextInt((int) (max - min + 1)) + min;
  System.out.println("ret = " + ret);
  return ret;
} 

但是,结果并不准确,例如:

找不到100个数字加起来4194304.最终总和= 4194305.0

我想我在这方面失去了准确性:

(sum * ret[i]) / iniSum

您能否在我的代码中推荐替代算法或修复程序,以帮助我实现此目标？

Answer 1

每次使用缩放值时ret[i] = Math.round((sum * ret[i]) / iniSum),都会失去一些精度,部分来自除法运算本身,但主要是将缩放值存储为整数.后一种情况类似于比例选举制度,其中少数席位必须分配给更多的选票.

减轻这种情况的两种方法:

首先缩放列表中的所有值,但要跟踪理想缩放值(实数)和存储的缩放值之间的差异.使用截断而不是舍入,使得差异始终是正的.如果存在差异,您可以按理想量和当前存储量之间的差值的顺序递增一些值.

long finSum = 0;  // Might as well be a long
float[] idealValues = new float[size];
for (int i = 0 ; i < ret.length; i++) {
    ideal[i] = (sum * ret[i]) / iniSum;
    ret[i] = (long) (ideal[i]);  // Truncate, not round
    System.out.println("ret[" + i +"] = " + ret[i]);
    finSum += ret[i];
}

/* There are iniSum - finSum extra amounts to add. */
for (int i = 0; i < iniSum - finSum; i++)
{
    /* Pick a target slot to increment.  This could be done by keeping a priority queue. */
    int target = 0;
    float bestScore = 0.0;
    for (int j = 0; j < size; j++) {
        float score = (ideal[j] - ret[j])/ret[j];
        if (score > bestScore) {
            target = j;
            bestScore = score;
        }
    }

    /* Allocate an additional value to the target. */
    ret[target]++;
}

或者更简单地说,您可以将列表中的最后一个值设置为缩放后执行所有其他值.但是,这确实会使输出产生偏差.