-2

I need to come up with an array of n integers, ranging from 0 to n-1 such that the sum of all of them is n(n-1)/2. How should I do this?

One way that I tried doing it was I randomly picked the first n-1 numbers and then picked the last number in a way such that the sum was n(n-1)/2. If it was in the interval [0, n-1], then I was good. Otherwise, I would recursively just run the same function again. However, when I ran this, I got a StackOverflow Error because the recursion ran too many times (none of the lists I made worked).

Is there a better way to randomly generate such lists in Java?

Ken White
  • 123,280
  • 14
  • 225
  • 444
theGrind24
  • 1
  • a bit of basic maths and the fact that the sum of the first N (positive) integers = n(n + 1) /2 – Mitch Wheat Dec 01 '20 at 03:13
  • 3
    Think about it. You need `n` numbers. The range is `0` to `n-1` which is comprised of `n` numbers. You were basically given the answer – smac89 Dec 01 '20 at 03:16
  • You just need to verify that the sum of the numbers `0` to `n-1` is indeed `n(n-1)/2` – smac89 Dec 01 '20 at 03:18
  • So I am reading the comments and I think there is some confusion. Just to clarify with an example, if n = 5, then a couple of valid list would be [1, 1, 3, 1, 4] or [0, 1, 2, 3, 4]? Because if the list generated isn't just the list from 0 to n-1, then there would need to be repeated numbers. – Miguel Aragon Dec 01 '20 at 03:51
  • Does this answer your question? [Is there an efficient way to generate N random integers in a range that have a given sum or average?](https://stackoverflow.com/questions/61393463/is-there-an-efficient-way-to-generate-n-random-integers-in-a-range-that-have-a-g) – Peter O. Dec 06 '20 at 09:13

3 Answers3

2

Try the integers from 0 to n-1. Let n = 6

0 1 2 3 4 5     
n(n-1)/2 = 6(6-1)/2 = 6(5)/2 = 15
WJS
  • 36,363
  • 4
  • 24
  • 39
  • I don't think I was clear enough... I meant that I need to randomly generate a list that adds to n(n-1)/2 using java code. – theGrind24 Dec 01 '20 at 03:26
  • @ArjuntheMathematician I think OP doesn't care about repetitions, which if that's the case, then the real question is: _given `n`, how many ways are there to sum to `n(n-1)/2` using just the numbers `0` to `n-1`_. I think there are many ways this can happen. For example given `n = 6`, `n(n-1)/2 = 15`, then you can have the lists `1 1 1 2 5 5`, or `1 1 2 2 5 4`, or `1 2 2 2 5 3`, etc – smac89 Dec 01 '20 at 03:58
1

The trivial solution is to create list 0 through n - 1. (The sum of 0 through n - 1 is n(n - 1) / 2.)

If you want a randomized list, take the above list and shuffle it.

If you want a randomized list that isn't simply a permutation of the list 0 through n - 1:

  1. Start with the above list 0 through n - 1
  2. Shuffle the list.
  3. Repeatedly (until you have reached the required level of randomness) do the following:
    1. randomly select two existing list elements: a and b
    2. generate a random number r such that a + r < n and b - r >= 0
    3. a' <- a + r
    4. b' <- b - r

This can be done iteratively in O(n) operations ... depending on how random you need the result to be.

(I'm not sure how many times you need to repeat step 3 to get "sufficient" randomness, but I think it should be O(n) times.)

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • But they are still the same numbers. There is only one solution for any given value of `n` – WJS Dec 01 '20 at 03:34
  • No there isn't. The question doesn't say that the numbers need to be unique. And steps 3.2 and 3.3 adjusts pairs of numbers to remove the uniqueness. – Stephen C Dec 01 '20 at 03:36
  • this is just a quick side comment but do any of you know how to add code to an overleaf doc? – theGrind24 Dec 01 '20 at 03:36
  • Nope. No idea. What is overleaf? – Stephen C Dec 01 '20 at 03:36
  • @ArjuntheMathematician might wanna just ask a new question. – smac89 Dec 01 '20 at 03:37
  • @StephenC A bad assumption on my part. I had assumed they were unqiue. – WJS Dec 01 '20 at 03:37
  • (I also address the case where they need to be unique. Second paragraph.) – Stephen C Dec 01 '20 at 03:38
  • Your third method is a step that never stops. Can you explain how repeatedly doing this will never exceed the sum `n(n-1)/2`. – smac89 Dec 01 '20 at 03:39
  • Ah. Actually nvm, I just saw reread the last step – smac89 Dec 01 '20 at 03:40
  • Sorry no, I just tried an example and I'm pretty sure this is not going to work. For example given the range `0` to `99`, randomly pick `1` and `2`, then randomly generate `85`. Now add `(1 + 85) mod 100` is `86`, and subtract `(2 - 85) mod 100` is `17`. Adding `85 + 17` to the current sum will surely exceed the goal of `n(n-1)/2`. Can you just give an example, thanks – smac89 Dec 01 '20 at 03:47
  • You are correct. I didn't think it through carefully. Fixed. – Stephen C Dec 01 '20 at 03:50
0

One Solution:

import java.lang.Math;

...

public int[] solution(int n) {
    int[] solution = new int[n];
    int targetSum = (n * (n - 1)) / 2;
    int runningSum = 0;
    double avgRemainder = 0.0;
    for (int i = 0; i < n - 1; i++) {
        do {
            solution[i] = (int)(Math.random() * n);
            avgRemainder = (targetSum - runningSum - solution[i])/(n - (i + 1));
            if (avgRemainder >= 0.0 && avgRemainder <= (n - 1)) {
                runningSum += solution[i];
            }
        } while (!(avgRemainder >= 0.0 && avgRemainder <= (n - 1)));
    }
    solution[n - 1] = targetSum - runningSum;
    return solution;
}

This will generate a random number, but before adding it to the list of solutions, it will check to see if it will cause the remaining slots to average outside of the range of acceptable numbers, which includes overshooting the target sum.

The cons to this (particularly if order matters) is that it will cause funneling at the end, if you randomly generate large numbers at the beginning, then obviously the remaining numbers will loop until they are small enough to fit in the solution... for example:
If n = 5
If we randomly generate the first two numbers to be 4
[4, 4, ?, ?, ?]
Then this method will loop the 3rd random number until it is between 0 and 2, and if it is 2...
[4, 4, 2, ?, ?]
Then it will loop the remaining numbers until they are 0.
[4, 4, 2, 0, 0]

This should be fine with larger values of n, and it is iterative instead of recursive.

EDIT: So actually the very last item must be forced because there will only be one solution for solution[n-1]. I fixed the code above to add that because it was getting an: Exception in thread "main" java.lang.ArithmeticException: / by zero.

Miguel Aragon
  • 148
  • 1
  • 9
  • My gut feeling is that this is going to give a list with a disproportionately large number of zeros (at the end of the list). – Stephen C Dec 01 '20 at 05:02
  • That is what I originally thought too, but apparently the average of the total over all the slots is (n-1) / 2, or exactly half of the largest value in the list, so running it several times, I get a nice distribution of numbers. – Miguel Aragon Dec 01 '20 at 05:09