2

I'm trying to produce four random numbers between 0 and 100 which will equal to 100.

I've managed to produce the outcome, but it isn't efficient. My method just keeps looping random numbers between 0-100, then adds them, if it doesn't equal to 100 then repeats the process until it equals to 100. Is there a more efficient method?

Thanks in advance

almost a beginner
  • 1,622
  • 2
  • 20
  • 41
  • [Show us your code.](http://stackoverflow.com/help/mcve) – spongebob Apr 16 '15 at 12:52
  • 1
    try devide and conquer: how would you produce two numbers that add up to 100? could you produce two numbers that go up to a randomly chosen number between 0 and 100? – BeyelerStudios Apr 16 '15 at 12:52
  • Can you not generate the first three then have the fourth make 100? – Slate Apr 16 '15 at 12:53
  • @kjhf what if the first three numbers add up to more than 100? – BeyelerStudios Apr 16 '15 at 12:53
  • 1
    You can also use random proportions. You start with 100 and split it in two, use random to know how big is one of the numbers vs the other. Then keep splitting one of those two until you reach the desired amount of random numbers. – Claudio Apr 16 '15 at 12:55
  • Can you please add a code example of what you already got and expand on what you intend to do, i don't think i can't be the only one a bit lost in this question. Is the objective to throw a 100-sided dice over and over and count how many times till it hits 100? – Felype Apr 16 '15 at 13:07

5 Answers5

6

You can generate your first random number between 1 and (100-3). Suppose your first random number is X. The next random number you generate should be between X and (100-2). Suppose that number is Y. The next random number should be between (X+Y) and (100-1). Suppose that number is Z.

Now you have your fourth random number which is 100-X-Y-Z. Double check a few of these to show that it has the same distribution as your current number generator to check your work.

Carlos Bribiescas
  • 4,197
  • 9
  • 35
  • 66
  • 1
    That **won't** yield the same distribution. – fabian Apr 16 '15 at 13:03
  • I think it will. This is basically the logic you could write after you generate all 4 numbers to validate it works. Can you explain why you think that? – Carlos Bribiescas Apr 16 '15 at 13:04
  • This sounds good, each next iteration is increasing the chance to hit a 100, may cause a lower range of possible results, not sure its what the OP intend tho, I don't really understand the question. – Felype Apr 16 '15 at 13:06
  • 1
    Original algorithm: obviously same probability for 1 to occuring as occuring as the third number. Your algorithm: `1 / 97` chance of 1 as first element and no chance of 1 as third number. – fabian Apr 16 '15 at 13:15
  • You're trying to say that numbers that match this constraint will have the same distribution as the original distribution. That is untrue. These numbers are generated from the original distribution, but then you throw out bunch of combinations that don't work. So the distribution is different than the original distribution, because of the constraint. Sure in the originally algorithm 1 can occur anywhere, but many of these will be thrown out. Which changes the distribution. – Carlos Bribiescas Apr 16 '15 at 13:20
  • Imagine you generated it in the originally way. You could sort the numbers, then apply my algorithm in order to determine if a combination will work or not. Right? The original just generates some extra random numbers unnecessarily while this prunes it as it goes. – Carlos Bribiescas Apr 16 '15 at 13:23
  • 1
    I was only seeking four pseudo random numbers that adds to 100, I didn't expect any advanced "even distribution" algorithm which would probably take me some time to learn. I chose this answer because 1. it works, 2. it was explained in a way that I could understand. Thanks for those who uploaded the code is well. – almost a beginner Apr 16 '15 at 13:30
5

Draw 3 numbers between 0 and 100 randomly without repetition. Now sort them ascending and interpret the gaps between subsequent numbers as the numbers you would have drawn in the first place. With using 3 dividers there are 4 gaps for 4 numbers you want to be drawn.

With this method you may have the same number multiple times, if that is ok for you.

SpaceTrucker
  • 13,377
  • 6
  • 60
  • 99
3

You can do this :

Random r = new Random();
int n1 = r.nextInt(100);
int n2 = r.nextInt(100 - n1);
int n3 = r.nextInt(100 - n1 - n2);
int n4 = 100 - n1 - n2 - n3;
Oussama Zoghlami
  • 1,660
  • 17
  • 24
2

This seems to work nicely:

Random random = new Random();

public int[] fourRandoms(int limit) {
    int[] randoms = new int[4];

    int[] three = new int[3];
    for (int i = 0; i < 3; i++) {
        three[i] = random.nextInt(limit);
    }

    int min = Math.min(three[0], Math.min(three[1], three[2]));
    int max = Math.max(three[0], Math.max(three[1], three[2]));
    int mid = three[0] + three[1] + three[2] - max - min;

    randoms[0] = min - 0;
    randoms[1] = mid - min;
    randoms[2] = max - mid;
    randoms[3] = limit - max;

    return randoms;
}

public void test() {
    for (int i = 1; i < 10; i++) {
        int[] randoms = fourRandoms(100);
        int sum = Arrays.stream(randoms).sum();
        System.out.println(Arrays.toString(randoms) + " = " + sum);
    }
}

It's an implementation of @SpaceTrucker's idea.

Alternatively - using Java 8 Streams.

public int[] nRandomsThatSumToLimit(int n, int limit) {
    return IntStream
            .concat(
                    // Stream n-1 random ints and sort them.
                    random.ints(n - 1, 0, limit).sorted(),
                    // Plus the final limit value.
                    IntStream.of(limit))
            // Convert into a stream of differences.
            .map(new IntUnaryOperator() {
                // Maintain the previous.
                int p = 0;

                @Override
                public int applyAsInt(int n) {
                    // Difference.
                    int d = n - p;
                    // Persist.
                    p = n;
                    return d;
                }
            }).toArray();
}
Community
  • 1
  • 1
OldCurmudgeon
  • 64,482
  • 16
  • 119
  • 213
  • Totally love the Streams solution! Did you come up with this yourself @OldCurmudgeon? – AndreasPizsa Aug 28 '18 at 09:53
  • @AndreasPizsa - Thank you. Sorry but I cannot recall where I got the idea. Note that this was 3 years ago. However, if you think about it, it does seem quite obvious. Take the differences between random numbers and make sure those differences add up to a specific value by making the last one the target number. – OldCurmudgeon Aug 28 '18 at 09:57
  • On further study it's actually just an extension of @SpaceTrucker's idea to `n` elements isn't it. – OldCurmudgeon Aug 28 '18 at 10:10
0

Generate 4 random numbers between 0 and 100
Sum the four numbers (s)
Divide each of the four generated numbers by s/100 (with rounding)
Your sum will now be 99, 100, 101
Adjust one of the random numbers up or down by one if needed checking that the adjustment does not fall below 0 or above 100

user2304484
  • 1