在二维数组中分配一组数字而不相邻的算法
Algorithm to distribute set of numbers in 2D array without neighboring themselves
我希望算法在已知维度的大二维数组中分配一组数字，例如 (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
如果您查看任何数字，您将永远不会看到它在任何方向上都与自己相邻？
我将描述一个算法来做你想做的事，希望能满足你的需要。
首先获取原始数字数组，然后根据需要将其拆分为 4 个大小大致相等的数组（在您的示例中，这可能看起来像 (0,1,2,3)， (4,5,6,7),(8,9,10,11),(12,13,14,15) 如果有意义的话）。将这些子数组分别标记为arr1、arr2、arr3、arr4。
现在，要填充数组，请按如下方式填充行：如果行是偶数索引（第零、第二、第四等），则将第一个元素填充到具有来自 arr1 的随机数的行，否则如果该行是奇数索引，则用第二个 arr3 中的数字填充该行。然后，用前一个 arr 中的随机数填充数组的下一个元素。例如，如果该行的第一个元素是来自 arr1 的数字，那么该行中的下一个元素将是 arr2 的元素，然后是 arr3 的元素，然后arr4，然后回到arr1，等等。就是这样。
为什么有效：如果您想知道它为什么有效，请首先将二维数组视为图形。包括对角线在内，2d 数组变成了 chromatic number 4 的图，这意味着它需要 4 个唯一元素才能 color 该图。这些颜色基本上就是 arr1, ..., arr4 的颜色，所以当用 arr 中的数字填充图表时，我们实际上是 "coloring" 图表。
要查看图形的着色方式，请考虑一个 4x4 数组。它可以是四种颜色：
[[ 1 , 2 , 3 , 4 ],
[ 3 , 4 , 1 , 2 ],
[ 1 , 2 , 3 , 4 ],
[ 3 , 4 , 1 , 2 ]]
请注意，这与上面的算法类似，但它不是从数字 1-4 中获取数字，而是从数组 arr1、...、arr4 中获取数字。还可以相对清楚地看到 4 着色对任何 m x n 数组都成立，证明了我们算法的有效性（这不是一个特别严格的证明，但希望你明白了）。
有几点需要注意。首先，你需要一个长度至少为 4 的初始数组，否则如果你不这样做，你将有不到 4 "colors" 可以使用，而且很容易看出你不能只用 3 给这个图着色颜色。此外，这个算法肯定可以改进，比方说，现在看起来 "more random"，虽然数字是平均分布的，但它们看起来不是很随机，例如来自 arr1 的数字会只能在最终数组的某些地方找到。但是，该算法确实大致平均分配了数字（最好是 arr1、arr2、arr3、arr4 的大小都相同）并且按照问题的要求进行操作，所以我相信它是有效的。
有关图形着色的更多阅读，我建议阅读相关的 Wikipedia page (more math intensive), or this 很酷的问题（4 色图定理，也许您熟悉它？）。
希望本回答对您有所帮助，如有问题请留言。
我希望算法在已知维度的大二维数组中分配一组数字，例如 (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
如果您查看任何数字，您将永远不会看到它在任何方向上都与自己相邻？
我将描述一个算法来做你想做的事，希望能满足你的需要。
首先获取原始数字数组，然后根据需要将其拆分为 4 个大小大致相等的数组（在您的示例中，这可能看起来像 (0,1,2,3)， (4,5,6,7),(8,9,10,11),(12,13,14,15) 如果有意义的话）。将这些子数组分别标记为
arr1、arr2、arr3、arr4。现在，要填充数组，请按如下方式填充行：如果行是偶数索引（第零、第二、第四等），则将第一个元素填充到具有来自
arr1的随机数的行，否则如果该行是奇数索引，则用第二个arr3中的数字填充该行。然后，用前一个arr中的随机数填充数组的下一个元素。例如，如果该行的第一个元素是来自arr1的数字，那么该行中的下一个元素将是arr2的元素，然后是arr3的元素，然后arr4，然后回到arr1，等等。就是这样。
为什么有效：如果您想知道它为什么有效，请首先将二维数组视为图形。包括对角线在内，2d 数组变成了 chromatic number 4 的图，这意味着它需要 4 个唯一元素才能 color 该图。这些颜色基本上就是 arr1, ..., arr4 的颜色，所以当用 arr 中的数字填充图表时，我们实际上是 "coloring" 图表。
要查看图形的着色方式，请考虑一个 4x4 数组。它可以是四种颜色：
[[ 1 , 2 , 3 , 4 ],
[ 3 , 4 , 1 , 2 ],
[ 1 , 2 , 3 , 4 ],
[ 3 , 4 , 1 , 2 ]]
请注意，这与上面的算法类似，但它不是从数字 1-4 中获取数字，而是从数组 arr1、...、arr4 中获取数字。还可以相对清楚地看到 4 着色对任何 m x n 数组都成立，证明了我们算法的有效性（这不是一个特别严格的证明，但希望你明白了）。
有几点需要注意。首先，你需要一个长度至少为 4 的初始数组，否则如果你不这样做，你将有不到 4 "colors" 可以使用，而且很容易看出你不能只用 3 给这个图着色颜色。此外，这个算法肯定可以改进，比方说，现在看起来 "more random"，虽然数字是平均分布的，但它们看起来不是很随机，例如来自 arr1 的数字会只能在最终数组的某些地方找到。但是，该算法确实大致平均分配了数字（最好是 arr1、arr2、arr3、arr4 的大小都相同）并且按照问题的要求进行操作，所以我相信它是有效的。
有关图形着色的更多阅读，我建议阅读相关的 Wikipedia page (more math intensive), or this 很酷的问题（4 色图定理，也许您熟悉它？）。
希望本回答对您有所帮助，如有问题请留言。