用于在2D阵列中分配数字集而不相邻的算法

Question

我希望算法在一个具有已知维度的大二维数组中分配一组数字，如（0,1 ... 15），而不让数字邻近自身作为例子：

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 0  1  2  3  4  5  6  7

3  4  5  6  7  8  9  10 11 12 13 14 15 0  1  2  3  4  5  6  7  8  9  10

6  7  8  9  10 11 12 13 14 15 0  1  2  3  4  5  6  7  8  9  10 11 12 13

如果你看任何数字，你永远不会看到它在任何方向相邻吗？

Answer 1

我将描述一种算法，用于做你想做的事情，希望能满足你的需求。

1. 首先取出原始的数字数组，然后将它分成4个大小相等的数组（在你的例子中，这看起来像（0,1,2,3），（4,5,6,7）， （8,9,10,11），（12,13,14,15），如果这是有道理的）。分别标记这些子阵列arr1，arr2，arr3，arr4。
2. 现在，要填充数组，请按如下方式填充行：如果行是偶数索引（第零，第二，第四等），则使用arr1中的radnom数填充行中的第一个元素，否则如果该行是奇数索引，请用第二个arr3中的数字填充该行。然后，使用前一个arr中的随机数填充数组的下一个元素。例如，如果行的第一个元素是来自arr1的数字，则行中的下一个元素将是arr2的元素，以及来自arr3，然后arr4，然后返回arr1等的元素。这就是它。

为什么会起作用：如果您想知道它为什么会起作用，首先将2d数组视为图形。包括对角线，2d阵列成为chromatic number 4的图形，这意味着它需要4个独特的元素来color图形。这些颜色基本上是arr1，...，arr4，所以当用arr的数字填充图表时，我们有效地“着色”图形。

要查看图表的颜色，请考虑使用4x4阵列。它可以是四色的：

[[ 1 , 2 , 3 , 4 ],
 [ 3 , 4 , 1 , 2 ],
 [ 1 , 2 , 3 , 4 ],
 [ 3 , 4 , 1 , 2 ]] 

请注意，这与上述算法的作用类似，但不是数字1-4，而是从数组中获取数字，arr1，...，arr4。同样清楚的是，对于任何m x n阵列都可以看到4色，这证明了我们算法的有效性（这不是一个特别严格的证明，但希望你能得到这个想法）。

有一些事情需要注意。首先，你需要一个长度至少为4的初始数组，否则你将需要少于4个“颜色”，并且很容易看出你不能只用3种颜色对这个图形着色。此外，这个算法当然可以改进，比如现在看起来“更随机”，而数字分布均匀，它们看起来不是很随机，例如来自arr1的数字只能是发现在最后一个阵列的某些地方。然而，这个算法确实大致相等地分配数字（最好是arr1，arr2，arr3，arr4都是相同的大小）并且问题是什么，所以我认为它是有效的。

有关图形着色的更多阅读，我建议阅读Wikipedia page（更多数学密集型），或this相关的酷问题（4色图定理，也许你熟悉它？）。

希望这个答案有所帮助，如果你有任何问题，请留下评论问题。