程序设计理论:二维阵列的改组

Question

我和一个朋友正在考虑一个有趣的计算机科学问题。

您有一个简单的2D数组：

[  1,  2,  3,  4 ]
[  5,  6,  7,  8 ]
[  9, 10, 11, 12 ]
[ 13, 14, 15, 16 ]

现在接受这个数组，对数组中的所有元素进行洗牌：

[ 11,  5, 14, 10 ]
[  8,  2,  4, 16 ]
[ 15,  1,  3, 13 ]
[  6, 12,  9,  7 ]

一开始一个相当简单的概念。但是，如果我们再采取一步呢？现在，对原始数组进行洗牌，这样在原始数组中，在主方向上，新数组的任何元素都不会与它们相邻的项相邻。

我们的第一次洗牌失败了，因为1在2旁边，在原始数组中也在2旁边。

下面是一个工作示例：

[  7, 16, 13,  2 ]
[ 14,  3,  5,  8 ]
[  9,  1,  4, 11 ]
[ 12, 10, 15,  6 ]

还是不算太糟。现在是真正的问题！

再次对原始数组进行洗牌，这样数组中的任何元素都不会在它们在基数方向或通过对角线与其相邻的元素旁边。

我们的工作示例失败了，因为1紧邻5对角，而在原始数组中接近5。

一些想法：

1. 一个数组甚至可以确定吗？
2. 它是否取决于数组的大小？
3. 阵列需要对称吗？
4. 数组是否需要有偶数/奇数的元素？
5. 由N为大小为M的所有数组提供解决方案吗？
6. 如果存在解决方案，那么查找新数组的运行时间是多少？

你认为如何？

编辑

我惊讶地发现我的问题以“离题”结束。根据常见问题的说法，如果我的问题"...generally涵盖了一个特定的编程问题.“然后，它被允许被问，而不是“离题”。

我想问的问题是：

你能拿出一个2D数组并对它进行洗牌，这样在新的数组中就不会有任何成员在一起，包括对角线。

这不是一个好的编程问题吗？我强烈认为我的问题不应该结束。

Answer 1

1.Can an array even be determined?

• 当然，您可以通过转置到边缘使用Rn -> RN转换。

2.它是否取决于数组的大小？

• 您不能在MxM <= 3中这样做，所以是的。

3.阵列是否需要对称？

• 视情况而定*

数组是否需要有偶数/奇数的元素？

• 视情况而定*

5.对于M×N大小的所有数组，是否有一个解决方案？

• 视情况而定*

6.如果存在解决方案，那么查找新数组的运行时间是多少？

运行时间可以是O(N^2)，使用一个简单的转换(考虑作为O(1))。

• 这取决于是否将重复作为解决方案(包)的一部分( 设置)。

至于算法本身。虽然这似乎是一种很好的大脑锻炼方式，但听起来更像是家庭作业，所以你为什么不试着做一些具体的事情呢？