CODEWITHSUNDEEP
javaarraysalgorithmrandom
user2462068
user2462068

Reputation: 161

How do I generate random numbers in an array that add up to a defined total?

I need to randomly generate an array with 7 slots in Java. All these slots must have a value of at LEAST 1, but combined, have a total value of another defined number. They also all need to be an int value, no 1.5 or 0.9816465684646 numbers. Example:

int a=10;

int[] ar = new int[7]
ar[0] = 1
ar[1] = 1
ar[2] = 2
ar[3] = 2
ar[4] = 1
ar[5] = 2
ar[6] = 1

I want it to generate something like that, but if int a=15, all the numbers would total 15 in any order

Upvotes: 13

Views: 11499

Answers (4)

Lee Daniel Crocker
Lee Daniel Crocker

Reputation: 13171

The standard way to generate N random numbers that add to a given sum is to think of your sum as a number line, generate N-1 random points on the line, sort them, then use the differences between the points as your final values. To get the minimum 1, start by subtracting N from your sum, run the algorithm given, then add 1 back to each segment.

public class Rand {
    public static void main(String[] args) {
        int count = 8;
        int sum = 100;
        java.util.Random g = new java.util.Random();

        int vals[] = new int[count];
        sum -= count;

        for (int i = 0; i < count-1; ++i) {
            vals[i] = g.nextInt(sum);
        }
        vals[count-1] = sum;

        java.util.Arrays.sort(vals);
        for (int i = count-1; i > 0; --i) {
            vals[i] -= vals[i-1];
        }
        for (int i = 0; i < count; ++i) { ++vals[i]; }

        for (int i = 0; i < count; ++i) {
            System.out.printf("%4d", vals[i]);
        }
        System.out.printf("\n");
    }
}

Upvotes: 40

Kon
Kon

Reputation: 10810

A good way to achieve uniformity is, for example, to fill up a = 15 units into an 8 element array:

  1. Put 1 in each element in the array as this is your requirement, you have now 7 values left to distribute
  2. Roll a random number between 0 and the max index of the array, and add 1 to that element, and subtract 1 from 7. Do this until 7 goes down to zero.

In this way, you'll meet your minimum conditions by having each element have minimum value 1. Then you distribute the remaining totals in a completely random way.

Upvotes: 14

Data Masseur
Data Masseur

Reputation: 1193

My java is horrible, so I'm not providing the actual code here, as it would probably be wrong. I've done this exact thing in SQL before though, so I know it works...

  1. Let Y be the Total value you want the elements to add up to
  2. Begin a loop with variable Z going from 1 to X where X is the number elements in your array (here called AR)
  3. In the loop, set AR(Z) to a random number between 1 and Y-X+Z
  4. Subtract the new value from Y, so Y = Y - AR(Z)
  5. End loop : back to step 2, advancing Z by 1

Upvotes: 1

Omar Abdeldayem
Omar Abdeldayem

Reputation: 128

Adding on to what @Kon said, you could use two random numbers rather than one for more randomness. That is:

Fill every element in the array with the value 1
valuesToDistribute = a - array.length-1
randomIndex = Roll a number between 0 and array.length-1
randomValue = Roll a number between 1 and valuesToDistribute
Add to randomIndex the value randomValue
Subtract randomValue from valuesToDistribute
Repeat until valuesToDistribute = 0

Upvotes: 2

Related Questions