arrays - 在一个巨大的二维数组中填充随机位置

Question

有没有一个巧妙的算法，我可以用它来填充一个巨大的二维 n x n 数组中的随机位置，数组中有 m 个数整数而不填充占用的位置？在哪里 , 和

有点像这个伪代码:

int n;
int m;

void init(int new_n, int new_m) {
    n = new_n;
    m = new_m;
}
void create_grid() {
    int grid[n][n];

    int x, y;
    for(x = 1; x <= n; x ++) {
        for(y = 1; y <= n; y ++) {
            grid[x][y] = 0;
        }
    }

    populate_grid(grid);
}

void populate_grid(int grid[][]) {
    int i = 1;
    int x, y;

    while(i <= m) {
        x = get_pos();
        y = get_pos();

        if(grid[x][y] == 0) {
            grid[x][y] = i;
            i ++;
        }
    }
}

int get_pos() {
    return random() % n + 1;
}

...但对于更大的 n 和 m 更有效。特别是如果 m 更大并且更多的位置被占用，生成一个未被占用的随机位置将需要更长的时间。

Answer 1

除非填充因子真的变大，否则您不必担心会碰到已占用的位置。

例如假设一半的单元格已经被填充，您有 50% 的机会首先点击一个填充的单元格；和 25% 连续击中两个填充的； 12.5% 的三分命中率……平均而言，需要……两次尝试才能找到空位! (更一般地说，如果只有一小部分 1/M 的空闲单元格，则平均尝试次数会增加到 M。)

如果您绝对想避免必须测试单元格，您可以通过使用空闲单元格的索引初始化一个数组来工作。然后，您不是选择随机单元格，而是选择数组中的随机条目，介于 1 和 L(列表的长度，最初为 N²)之间。

选择条目后，设置相应的单元格，将列表中的最后一个元素移动到随机位置，并设置 L= L-1。这样，空闲职位列表就会保持最新。

请注意，此过程的效率可能低于盲目尝试。