按交换方式排序二维数组的算法

Question

对于一维数组，可以通过使用冒泡排序轻松实现交换排序，例如：

5 4 9 8 7 1 6 3 2 10

需要进行25次交换才能输出结果

1 2 3 4 5 6 7 8 9 10

在二维数组中，我们有如下内容。

4 2 3
1 8 5
7 9 6

项目可以垂直和水平交换，但不能对角线交换：

• 交换4和1
• 交换8和5
• 交换8和6
• 交换9和8

这将成为排序后的数组：

1 2 3
4 5 6
7 8 9

我正在寻找一种可以高效实现这个目标的算法（最小化交换次数）。这个问题可能与15谜题类似，但是它要简单得多，因为每个项目都可以与相邻的项目交换，而不仅仅是与空白块交换。

- JCarter

---

你没有明确定义所谓的排序是什么。为什么结果数组看起来像你的，为什么会有任意的限制？ - HopefullyHelpful

@HopefullyHelpful 这个数组是一个n×n的多维数组，其中填充了n*n个不同的数字。这些数字需要按行以升序排序；但是，每一行的第一个数字必须大于前一行的最后一个数字（所有数字中最小的数字将在[0,0]位置）。 - JCarter

"JCarter，一个实现最小交换次数的算法将非常低效。修改冒泡排序已经很低效了，但使用2D数组会使运行时间变得非常糟糕。相反，使用一个针对1D数组的排序算法修改，将2D数组索引映射到等价的1D数组索引。" - user4668606

第三次交换是将8和6交换，而不是5和6。 - rcgldr

@HopefullyHelpful 这是链接：http://codegolf.stackexchange.com/questions/69642/sort-scrambled-two-dimensional-array-filled-with-numbers-by-swapping - JCarter

Answer 1

在一维数组中，冒泡排序只交换相邻元素，同时也只比较相邻元素。但是在二维数组中，没有类似的方法可以使用，因为你无法检测到。

1 2 4
3 5 6
7 8 9

出现故障了（因为您无法直接比较非相邻的3和4）。

如果我们说您可以检查和比较任意元素，但是更新元素的唯一方法是将其与其邻居之一交换，那么最好的方法是首先完全确定每个元素需要到达的位置（例如，通过将元素复制到常规数组中并应用标准排序算法），然后仅执行必要的交换以将元素移动到它们的目标位置。

- ruakh

Answer 2

如果您有一个3 x 3的矩阵，那么就有9个元素，也就是说有9!=362880种可能的交换情况。而如果矩阵是4 x 4，那么就有16！即20,922,789,888,000种可能的交换情况。您可以看到这个规律。不幸的是，这是一个非常困难的问题，属于NP-Hard问题，实际上不能在多项式时间内解决。目前为止就像15Puzzle一样。交换任何元素都应该具有较少的步骤，从而使其更容易找到解决方案。
然而，您可以尝试使用知情搜索（informed search）来寻找解决方案。定义一个好的启发式函数来表示当前状态与目标状态之间的距离，并在例如A* 搜索中使用它。这是您可以做的最简单的事情。您可以尝试一些稍微复杂一点的算法，例如Alpha-Beta剪枝。作为启发式函数，我建议计算每个项与其目标位置之间的曼哈顿距离。
例如，

4 2 3
1 8 5
7 9 6

数字4位于[0][0]位置，应该在1的位置，所以4的汉明距离是（1-0）+（1-0）=2。这意味着你需要至少交换两次才能将4移到正确的位置。并且你要对所有9个元素进行汉明距离求和。这就是你的状态分数。

此外，在选择下一个状态时，请务必使用优先队列，在每个步骤中从前沿采样最佳的后继状态是O(1)的，但是添加新的后继状态是O(logn)的。

祝好！

- Ammar Rashed