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

Assume you have a n x m matrix. In this matrix, you will be randomly positioning FOUR different objects say a, b, c, d. There will be many of each.

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

Now what is the best algorithm so that when they are randomly placed, their positions don't *?

现在什么是最好的算法,以便当它们随机放置时,它们的位置不会发生冲突?

My approach would be to:

我的方法是:

Randomly place them

随机放置它们

Check through all the object's position, and if they *, keep on moving until an empty space is found?

检查所有物体的位置,如果它们发生碰撞,继续移动直到找到空的空间?

I am just wondering if there is any other efficient solution.

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

3 个解决方案

#1

If the end goal is to fill the board, you could just choose for each space on the matrix which type goes on it (the choice is random).

如果最终目标是填充板,您可以选择矩阵上的每个空间(类型是随机的)。

To add an option of an empty space, add a fifth option of NO_TYPE.

要添加空白空间的选项,请添加NO_TYPE的第五个选项。

If the number of appearances is known, try this:

如果已知出现次数,请尝试以下操作:

Create a list of size n X m (call it L) with values 1..L.

使用值1..L创建大小为n X m(称为L)的列表。
For each appearance, choose randomly from the list ( something like pos = rand(L) and the remove that value form the list (don't forget to decrease L).

对于每个外观,从列表中随机选择(类似pos = rand(L)并从列表中删除该值(不要忘记减少L)。
Do this as many times as the necessary.

尽可能多次这样做。

#2

A variation on the other answer, without creating additional structure (and with a better time complexity) :

另一个答案的变体,没有创建额外的结构(并且具有更好的时间复杂度):

Let assume that you have objects a_1, .., a_K (in your case K=4) and each of them has to be present n_k times, with n_1 + .. + n_K <= n*m. You can fill the matrix as follows, in pseudocode :

假设您有对象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

This will work better than your approach if you have many objects to place as you never reject placements. If you don't, then your approach is fine.

如果您有许多对象要放置,因为您从不拒绝放置,这将比您的方法更好。如果你不这样做,那么你的方法很好。

#3

If you have an algorithm that can generate a sequence of random positions that don't * in your array, then you can easily generate however many positions you need for a then b then c then d etc.

如果你有一个算法可以生成一系列不会在你的数组中发生冲突的随机位置,那么你可以很容易地生成你需要的多个位置然后是b然后是c然后等等。

You can accomplish this with this algorithm:

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

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)
}

The positions will never overlap because there are no common factors between p and n * m. It will produce a Full Cycle over n * m

位置永远不会重叠,因为p和n * m之间没有共同因素。它将产生超过n * m的全周期

For how to generate a random prime number, see this * question:

有关如何生成随机素数,请参阅此*问题:

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

在C / C ++中生成2个限制之间的随机素数

If p is prime, then it will be relatively prime with n * m

如果p是素数,那么它将是n * m的相对素数

#1