Java 7+, n=50 in ~30 sec on TIO
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Random;
class Main{
public static void main(String[] a){
int n=50;
Random randomGenerator = new Random();
int i = n+1;
int squaredN = n*n;
int[]randomIntegers = new int[i];
randomIntegers[n] = squaredN;
while(true){
for(i=n; i-->1; ){
randomIntegers[i] = randomGenerator.nextInt(squaredN);
}
Set<Integer> result = new HashSet<>();
Arrays.sort(randomIntegers);
for(i=n; i-->0; ){
result.add(randomIntegers[i+1] - randomIntegers[i]);
}
if(!result.contains(0) && result.size()==n){
System.out.println(result);
return;
}
}
}
}
Ungolfed version of my answer for the code-golf version of this challenge for now, with only one minor change: java.util.Random#nextInt(limit)
is used instead of (int)(Math.random()*limit)
for an integer in the range [0, n)
, since it's about twice as fast.
Try it online.
Explanation:
Approach used:
The code is split into two parts:
- Generate a list of
n
amount of random integers that sum to n squared
.
- Then it checks if all values are unique and none are zero, and if either is falsey, it will try step 1 again, rinsing and repeating until we have a result.
Step 1 is done with the following sub-steps:
1) Generate an array of n-1
amount of random integers in the range [0, n squared)
. And add 0
and n squared
to this list. This is done in O(n+1)
performance.
2) Then it will sort the array with the builtin java.util.Arrays.sort(int[])
, This is done in O(n*log(n))
performance, as is stated in the docs:
Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
3) Calculate the difference between each pair. This resulting list of differences will contain n
integers that sum to n squared
. This is done in O(n)
performance.
Here an example:
// n = 4, nSquared = 16
// n-1 amount of random integers in the range [0, nSquared):
[11, 2, 5]
// Add 0 and nSquared to it, and sort:
[0, 2, 5, 11, 16]
// Calculate differences:
[2, 3, 6, 5]
// The sum of these differences will always be equal to nSquared
sum([2, 3, 6, 5]) = 16
So these three steps above are pretty good for performance, unlike step 2 and the loop around the whole thing, which is a basic brute-force. Step 2 is split in these sub-steps:
1) The differences list is already saved in a java.util.Set
. It will check if the size of this Set is equal to n
. If it is, it means all random values we generated are unique.
2) And it will also check that it contains no 0
in the Set, since the challenge asks for random values in the range [1, X]
, where X
is n squared
minus the sum of [1, ..., n-1]
, as stated by @Skidsdev in the comment below.
If either of the two options above (not all values are unique, or a zero is present), it will generate a new array and Set again by resetting to step 1. This continues until we have a result. Because of this, the time can vary quite a bit. I've seen it finish in 3 seconds once on TIO for n=50
, but also in 55 seconds once for n=50
.
Prove of uniformity:
I'm not entirely sure how to prove this to be completely honest. The java.util.Random#nextInt
is uniform for sure, as is described in the docs:
Returns the next pseudorandom, uniformly distributed int
value from this random number generator's sequence. The general contract of nextInt
is that one int
value is pseudorandomly generated and returned. All 232 possible int
values are produced with (approximately) equal probability.
The differences between these (sorted) random values themselves are of course not uniform, but the sets as a whole are uniform. Again, I'm not sure how to prove this mathematically, but here is a script that will put 10,000
generated sets (for n=10
) in a Map with a counter, where most sets are unique; some repeated twice; and the maximum repeated occurrence is usually in the range [4,8]
.
Installation instructions:
Since Java is a pretty well-known language with plenty of information available on how to create and run Java code, I will keep this short.
All the tools used in my code are available in Java 7 (perhaps even already in Java 5 or 6, but let's use 7 just in case). I'm pretty sure Java 7 is already archived though, so I would suggest downloading Java 8 to run my code.
Thoughts regarding improvements:
I'd like to find an improvement for the check for zeros and check all values are unique. I could check for 0
before, by making sure the random value we add to the array isn't already in it, but it would mean a couple of things: the array should be an ArrayList
so we can use the builtin method .contains
; a while-loop should be added until we've found a random value that isn't in the List yet. Since checking for zero is now done with .contains(0)
on the Set (which is only checked once), it's most likely better for performance to check it at that point, in comparison to adding the loop with .contains
on the List, which will be checked at least n
times, but most likely more.
As for the uniqueness check, we only have our n
amount of random integers that sum to n squared
after step 1 of the program, so only then we can check whether all are unique or not. It might be possible to keep a sortable List instead of array, and check the differences in between, but I seriously doubt it will improve the performance than just putting them in a Set
and check if the size of that Set is n
once.