How to generate a sequence of n random positive integers which add up to some value?

Question

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:

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?

Answer 1

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.

Answer 2

Just got an idea. Initialize the array to all 0. Randomly pick a number in the array and increase by 1 and decrease sum by 1 until sum is 0. It's not practical at all when sum is large:)

long ret = new long[size];
for(int i=0;i<size;i++) ret[i]=0;
for(int i=0;i<sum;i++) {
  int n = random(0,size);
  ret[n]++;
}