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

Question

编辑: 这个问题已经解决了。如果您想帮助解决其他问题，请访问 Java Biasing Random Numbers in a Triangular Array .

---

我在玩乘法游戏，所以我选择了 0 到 12 之间的 2 个数字(含 0 和 12)。如果我这样做:

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

方 block (0x0、1x1、2x2 等)有一半时间被选中(因为 1x2 与 2x1 相同)。我怎样才能让所有的组合都以相同的频率被选中？有 91 种可能的组合 (n(n+1)/2)。如果有帮助，这是一个 13 x 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) 策略可以正常工作。您将获得有保证的、无忧的均匀分布和更好的启动性能，因为您只选择了 1 个随机数。您只需要找到一个公式来标识一个“行”的结束位置和另一个“行”的开始位置。寻找模式:

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

它们被称为 "triangular numbers..." 是有原因的

让我们更充实一点。您实际上想要找到比您选择的随机 roll 最近的三角形编号更小:这会让您到达正确的行，以及该三角形编号与 roll 获取该行的偏移量。

鉴于 n^th 三角形数由 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!

---

_{*假设 native StrictMath#sqrt(double)函数是常数时间 - I'm actually not sure about this.}