如何生成一个n个随机正整数序列，它们加起来有些值？ [英] How to generate a sequence of n random positive integers which add up to some value?

问题描述

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

I'm trying to generate an array of integers contains randoms adding up to a particular value. Here's my code:

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;
} 

然而，结果并不准确，例如：

However, the results are not accurate, for instance:

找不到100个数字，最多为4194304。最终总和=
4194305.0

Could not find 100 numbers adding up to 4194304 . Final sum = 4194305.0

我认为我在这方面失去了准确性：

I think I'm losing accuracy in this bit:

(sum * ret[i]) / iniSum

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

Can you recommend an alternative algorithm or a fix in my code which can help me achieve this objective?

推荐答案

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

Each time you scale a value with ret[i] = Math.round((sum * ret[i]) / iniSum), you will lose some precision, partly from the division operation itself, but mostly from storing the scaled value as an integer. The later situation is similar to proportional electoral systems where a small number of seats must be allocated in proprtion to a larger numbers of votes.

两种减轻这种情况的技巧：

Two techniques for mitigating this:

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

First scale all the values in the list, but keep track of the difference between the ideal scaled value (a real number) and stored scaled value. Use truncation instead of rounding, so that the discrepency will always be positive. If there is a discrepency, you can increment some of the values in order of the difference between the ideal amount and the current stored amount.

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]++;
}

或者更简单地说，你可以将列表中的最后一个值设置为在完成所有其他工作之后，它是出色的。但是，这确实会使输出产生偏差。

Or more simply, you could just set the last value in the list to whatever is outstanding after scaling doing all the others. That does statistically skew the output, however.

这篇关于如何生成一个n个随机正整数序列，它们加起来有些值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！