Dividing a number into smaller random ints

Question

So what i need is basically described in the subject.

Like if i would put in number 12 and amount of parts it should devide into, i would like it to return something like (with 4 parts) 8, 2, 1, 1. But not doubles because i need the values as int.
I had found one answer earlier but it only worked using doubles. not ints.
(this is the one i found)

public double[] divideUniformlyRandomly(double number, int part) {
    double uniformRandoms[] = new double[part];
    Random random = new Random();
    double mean = number / part;
    double sum = 0.0;
    for (int i=0; i<part / 2; i++) {
        uniformRandoms[i] = random.nextDouble() * mean;
        uniformRandoms[part - i - 1] = mean + random.nextDouble() * mean;
        sum += uniformRandoms[i] + uniformRandoms[part - i -1];
    }
    uniformRandoms[(int)Math.ceil(part/2)] = uniformRandoms[(int)Math.ceil(part/2)] + number - sum;
    return uniformRandoms;

I had tried changing this code to work using Ints by doing this:

public int[] divide(int number) {
    int part = getDivider(number);
    int uniformRandoms[] = new int[part];
    Random random = new Random();
    int mean = number / part;
    int sum = 0;
    for (int i=0; i<part / 2; i++) {
        uniformRandoms[i] = random.nextInt() * mean;
        uniformRandoms[part - i - 1] = mean + random.nextInt() * mean;
        sum += uniformRandoms[i] + uniformRandoms[part - i -1];
    }
    uniformRandoms[(int)Math.round(part/2)] = uniformRandoms[(int)Math.round(part/2)] + number - sum;
    for(int i : uniformRandoms)
        System.out.println(i);
    return uniformRandoms;
}

But when running that using number: 512 and using 10 parts (getDivider() will return 10) itll output this:

-1058809647, -2102647561, 469849949, 1627965716, -290084223, -33347991

And alot more of this kind of numbers.

Thanks.

Answer 1

Here's an algorithm which will do the job:

1. Create an array of length parts+1.
2. Add the values 0 and number to the array, then fill the remainder of it with unique random values using random.nextInt(number-1) + 1 to get values between 0 and number exclusive of the range limits.
3. Sort the array.
4. Iterate through the sorted array starting at index 1. The successive differences array[i] - array[i-1] will be a set of positive integers that sum to number.

If zeros are allowed, then you don't need the uniqueness criterion in filling the array. If you need uniqueness, you might consider adding random values to a HashSet (which only .add()'s unique entries) until the size meets your requirement, then convert it with .toArray().

Here's an actual implementation:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;

public class SumToTotal {
   public static Random r = new Random();

   public static int[] divide(int number, int number_of_parts) {
      HashSet<Integer> uniqueInts = new HashSet<Integer>();
      uniqueInts.add(0);
      uniqueInts.add(number);
      int array_size = number_of_parts + 1;
      while (uniqueInts.size() < array_size) {
         uniqueInts.add(1 + r.nextInt(number - 1));
      }
      Integer[] dividers = uniqueInts.toArray(new Integer[array_size]);
      Arrays.sort(dividers);
      int[] results = new int[number_of_parts];
      for(int i = 1, j = 0; i < dividers.length; ++i, ++j) {
         results[j] = dividers[i] - dividers[j];
      }
      return results;
   }

   public static void main(String[] args) {
      System.out.println(Arrays.toString(divide(12, 5)));
   }
}

This produces results such as [3, 2, 1, 2, 4] or [1, 5, 2, 3, 1].

Answer 2

A inefficient but very easy way would be to loop n times and increment one of the indices by one.

    void divider(int number, int divisions)
    {
        Random rand = new Random();
        int[] container = new int[divisions];

        System.out.print(number + "->");
        while (number > 0)
        {
            container[rand.nextInt(divisions)]++;
            number--;
        }
        for (int i : container)
        {
            System.out.print("[" + i + "]");
        }
    }

divider(1000, 20) could output:

1000->[57][43][60][35][39][47][45][59][51][71][52][54][58][48][33][49][49][46][49][55]
1000->[60][50][49][53][42][52][52][45][40][51][52][51][53][47][51][46][53][56][45][52]
1000->[52][43][49][53][57][45][42][43][61][61][58][44][46][49][52][39][63][45][54][44]

On my way to old PC it takes only 11ms to divide 100.000 in 20 different "containers". So if you are not using this very often and/or on very big numbers this is a perfectly valid way to do it.

Answer 3

Assuming every term should at least be 1.

public int[] divide(int number, int parts) {
    int[] randoms = new int[parts];
    Arrays.fill(randoms, 1); // At least one
    int remainder = number - parts;
    Random random = new Random();
    for (int i = 0; i < parts - 1 && remainder > 0; ++i) {
        int diff = random.nextInt(remainder);
        randoms[i] += diff;
        remainder -= diff;
   }
   randoms[parts - 1] += remainder;
   Arrays.sort(randowms);

   // Reverse (for getting a descending array):
   for (int i = 0, j = parts - 1; i < j; ++i, --j) {h
       int temp = randoms[i];
       randoms[i] = randoms[j];
       randoms[j] = temp;
   }
   return randoms;
}

This is not uniformly distributed. For that one could iterate till remainder becomes 0, everytime randomly picking an index to increase. Or so. Have fun.

Was this homework?

Answer 4

Use Random#nextInt(int)

public int[] divideUniformlyRandomly(int number, int parts) {
    Random random = new Random();
    int[] randoms = new int[];
    for(int i = 0; i < parts; i++) {
        randoms[randoms.length] = random.nextInt(number);
    }
    return randoms;
}