Java-Math.random(): выбор элемента из треугольной решетки 13 на 13

Question

Редактировать: Данная проблема решается. Если вы хотите помочь в решении другой проблемы, посетите Java Biasing Random Numbers in a Triangular Array.

Я занимаюсь умножением, поэтому я выбираю 2 числа от 0 до 12 включительно. Если бы я сделать это так:

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

квадраты (0x0,1x1,2x2 и т.д.) собирают половину времени (потому что 1х2 такая же, как 2х1). Как я могу сделать все комбинации, выбранные на той же частоте? Имеются 91 возможные комбинации (n (n + 1)/2). Если это помогает, вот 13 по 13 треугольный массив:

{{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}}; 

Я пытался выбирать первое число и дает второе число на 50% шанс быть первым. Это не сработало. Я попытался дать второе число 1/91 шанс стать первым. Это привело к тому, что меньшие числа были выбраны гораздо большим количеством раз (около 7/91 времени, это плавное, изогнутое увеличение). Я думал о наличии единственного случайного числа: int roll = random.next(91), а затем разбил его на 2 записи (например, координату (x, y)), но я не мог понять, как разбить ее.

Answer 1

Стратегия int roll = random.next(91) будет работать нормально. Вы получаете гарантированное равномерное распределение без проблем и более высокую производительность для загрузки, поскольку вы выбираете только одно случайное число. Вам просто нужно найти формулу, которая идентифицирует, где заканчивается одна «строка», а другая начинается. Посмотрите на шаблон:

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

Там причина, они называются "triangular numbers..."

Давайте плоть на это немного больше. Вы действительно хотите найти ближайший треугольный номер меньше, чем случайный roll, который вы выбрали: это приведет вас к правильной строке, а разница в этом треугольном номере и roll получает смещение в эту строку.

Учитывая, что n^{е число} треугольник задается n*(n+1)/2, как найти самый большой один меньше, чем roll? Учитывая небольшой размер массива, наивная реализация должна быть много быстро:

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

Конечно, это скучное и не принимать какую-либо мысли. Мы можем сделать лучше! Мы можем делать это в постоянном * времени, независимо от того, насколько велик вход!Начните inverting the function (мы только заботиться о положительный корень, конечно):

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

Затем усечение дробной части, и запустить его обратно через:

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

http://ideone.com/1qBHfX

Выражаясь все вместе:

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

That's it!

---

_{* при условии, что родная StrictMath#sqrt(double) функции постоянное времени - I'm actually not sure about this.}