避免矩阵算法中的位置冲突

Question

假设您有一个 n x m 矩阵。在此矩阵中，您将随机放置四个不同的对象，例如 a、b、c、d。每个都会有很多。

现在最好的算法是什么，当它们随机放置时，它们的位置不会冲突？

我的方法是：

随机放置
检查所有物体的位置，如果它们发生冲突，继续移动直到找到一个空的space？

我只是想知道是否还有其他有效的解决方案。

Answer 1

如果最终目标是填满棋盘，您可以为矩阵上的每个 space 选择其上的类型（选择是随机的）。

要添加空选项 space，请添加第五个选项 NO_TYPE。

如果知道出现次数，试试这个：

创建一个大小为 n X m 的列表（称之为 L），值为 1..L.
对于每次出现，从列表中随机选择（例如 pos = rand(L) 并从列表中删除该值（不要忘记减少 L).
根据需要多次执行此操作。

Answer 2

另一个答案的变体，没有创建额外的结构（并且具有更好的时间复杂度）：

假设您有对象 a_1, .., a_K（在您的情况下，K=4）并且每个对象都必须出现 n_k 次，其中 n_1 + .. + n_K <= n*m。您可以在伪代码中按如下方式填充矩阵：

Initialize X as an empty n*m matrix
Initialize n as a vector of length l with n[l] = n_l
Set N = 0
For i = 1; i <= n; i++
    For j = 1; j <= m; j++
        Draw t at random uniformly on [0,1]
        For l = 1; l <=k; l++
            Set x_l = n[l] / (n*m-N)
            If (t <= x_l)
                Set X[i][j] = a_l
                Set n[l] = n[l]-1
                Escape the loop on l
     Set N = N+1

如果您有很多对象要放置，这会比您的方法更有效，因为您从不拒绝放置。如果你不这样做，那么你的方法就可以了。

Answer 3

如果您有一种算法可以生成一系列随机位置，这些位置不会在您的数组中发生冲突，那么您可以轻松生成 a 所需的任意位置，然后b 然后 c 然后 d 等等

您可以使用此算法完成此操作：

Generate a random prime number p that is greater than n * m
Generate a random number r in the range [0, n * m)
while(need more numbers)
{
    // output a position:
    yield x = r % n, y = r / n

    // generate the next position:
    r = (r + p) % (n * m)
}

位置永远不会重叠，因为p和n * m之间没有公因数。它将在 n * m

上产生 Full Cycle

关于如何生成随机素数，请参阅这个 Whosebug 问题：

Generate Random Prime number in C/C++ between 2 limits

若p为质数，则与n * m互质

另见这个问题：

How can I randomly iterate through a large Range?

避免矩阵算法中的位置冲突

Avoid clash of positions in a matrix algorithm

algorithm

matrix

neighbours

nearest-neighbor