13

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

2
  • This might even be worth an algorithm tag.
    – Cruncher
    Commented Sep 3, 2013 at 19:51
  • OP, do you know about random variables and probability distributions? This question can't be answered until you define more precisely what you mean by random. Commented Sep 9, 2013 at 15:28

4 Answers 4

40

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");
    }
}
14
  • That's very interesting
    – Cruncher
    Commented Sep 3, 2013 at 20:16
  • Could you show a little code so I can see what would be going on? Commented Sep 3, 2013 at 20:27
  • Yeah, I should probably show some code. Give me a few minutes. Commented Sep 3, 2013 at 20:36
  • This is a good approach, but the problem is a little harder when the numbers are constrained to be integers. The devil will be in the details.
    – Ted Hopp
    Commented Sep 3, 2013 at 20:37
  • @TedHopp I'm not sure why the integerness makes a problem. The average difference between the numbers is still going to be N/sum
    – Cruncher
    Commented Sep 3, 2013 at 20:46
14

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.

16
  • +1, don't see any better possible solution. I was pondering on how to get uniformity. My plight here is that they may be too uniform. For a sufficiantly large a, all numbers are going to be very close together, to the point where it's hard to tell there was any randomness.
    – Cruncher
    Commented Sep 3, 2013 at 19:52
  • So what would I change from what you said to make it a 7 element array? I only need 7 numbers Commented Sep 3, 2013 at 19:56
  • 3
    This will perform terribly when your sum is very large. Commented Sep 3, 2013 at 20:16
  • 1
    @LeeDanielCrocker The OP said his values will not exceed 99.
    – Kon
    Commented Sep 3, 2013 at 20:17
  • 1
    This is going to be slow when a is large. A far more efficient solution would be the one described by Lee Daniel Crocker. Commented Sep 3, 2013 at 20:25
2

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
1

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
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.