Java-Math.random (): element selection of a 13 by 13 triangular array

Question

Edit: This issue has been resolved. If you want to help solve another problem, go to Java Random Numbers in a three-dimensional array .

---

I make a multiplication game, so I select 2 numbers from 0 to 12 inclusive. If I do this:

int num1 = (int)(Math.random() * 13); int num2 = (int)(Math.random() * 13); 

squares (0x0,1x1,2x2, etc.) are selected halfway (because 1x2 is the same as 2x1). How can I make all combinations selected on the same frequency? There are 91 possible combinations (n ​​(n + 1) / 2). If that helps, here is a 13 by 13 triangular array:

 {{0}, {0,0}, {0,0,0}, {0,0,0,0}, {0,0,0,0,0}, {0,0,0,0,0,0}, {0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0}}; 

I tried to choose the first number and give the second number a 50% chance of becoming the first. This did not work. I tried to give the second number 1/91 a chance to become the first. This led to the fact that smaller numbers were chosen much more times (about 7/91 of the time, this is a smooth, curved increase). I was thinking about having one random number: int roll = random.next(91) , and then breaking it into 2 entries (for example, the coordinate (x, y)), but I could not figure out how to separate it.

Answer 1

The int roll = random.next(91) strategy will work int roll = random.next(91) fine. You get guaranteed even distribution without problems and better performance for loading, since you choose only one random number. You just need to find a formula that identifies where one “line” ends and the other begins. Find the template:

 0, 1, 3, 6, 10, 15, ... 

There is a reason why they are called "triangular numbers ..."

Let it be a little more. You really want to find the nearest triangle number, smaller than the random roll that you selected: this will lead you to the correct line, and the difference in this triangular number and roll gets an offset to this line.

Given that the number of triangles n ^th is given by n*(n+1)/2 , how do you find the largest size less than roll ? Given the small size of the array, the naive implementation should be pretty fast:

 int largestTriangleNumberSmallerThan(int x) { int i = 0; int last = 0; while (true) { int triangle = i*(i+1)/2; if (triangle > x) return last; last = triangle; i++; } } 

http://ideone.com/vzQEBz

Of course, it was boring and never thought of. We can do better! We can do this in constant * time, no matter how big the entrance! Start by inverting the function (of course, we only care about the positive root):

 n = (Math.sqrt(8y + 1) - 1)/2 

Then truncate the decimal part and run it through:

 int largestTriangleNumberSmallerThan(int x) { int n = (int) (Math.sqrt(8*x + 1) - 1)/2; return n*(n+1)/2; } 

http://ideone.com/1qBHfX

Combine all of this:

 int roll = random.nextInt(91); int num1 = (int) (Math.sqrt(8*roll + 1) - 1)/2; int num2 = roll - num1*(num1+1)/2; 

What is it!

---

_{*, assuming that the native function StrictMath#sqrt(double) is constant time - I'm really not sure about that.}