Matlab：删除矩阵中多余的“移位”条目

Question

我有一个问题需要解决，但我想不出任何简单和更重要的问题：快速解决方案。这有点像多旅行商问题的一部分。

首先我有X行和N列的矩阵，N是我的算法的静态变量和X可以改变。让我们假设它看起来像（这里N = 5）：

matrix = [1 2 4 3 5; 4 3 1 2 5; 1 2 4 3 5; ] 
matrix = 
1  2  4  3  5 
4  3  1  2  5 
1  2  4  3  5 

每一行被看作是一个“路线”，并包含1和N每个路由（=排）之间的所有独特的数字将在部分路径进行分割。这意味着，我有一个断点矩阵，其中包含X行和M（M < N）列。例如为：

breakpoints = [2 3 4; 1 2 4; 1 3 4] 
breakpoints = 
2  3  4 
1  2  4 
1  3  4 

的breakpoints各行得到的matrix对应的行之后的路线将被分割为部分路径中的元素的索引。为了说清楚，我们以第一行为例：breakpoints(1, :) = 2 3 4这意味着，路线matrix(1, :) = 1 2 4 3 5将被拆分为部分路线[1 2], [4], [3] and [5]。第二行具有断点breakpoints(2, :) = 1 2 4，该断点将第二条路线matrix(2, :) = 4 3 1 2 5拆分为部分路线[4], [3], [1 2] and [5]。

现在我的目标是从matrix中删除所有行，而部分路由是冗余重复的，只是顺序不同。在此示例中，第2行是第1行的副本。即使第3行与第1行具有相同的路由，第3行也不会重复，因为存在导致部分路由[1], [2 4], [3] and [5]的不同断点。

我该如何干净而快速地做到这一点？矩阵可以包含许多元素，如X = 5e4行和N = 10,M = 6。

Answer 1

对于常数M，N，可以通过将复合记录按顺序排序，然后测试相邻条目的相等性，在时间O（X log X）中解决此问题。

“复合记录”我的意思是一个记录，它将一个行的函数和它的断点组合成一个记录。通过以下方式获得对于给定行的功能：

1. 将断点应用于行，获取部分路由的列表。
2. 将部分路线按每个路线的第一个元素升序排序。 例如按{[1 2]，[3]，[4]，[5]}排序{[4]，[3]，[1 2]，[5]}。
3. 通过连接排序部分路由来形成新的组合记录;有效的断点;和一个索引到源行。 例如如果上一步中的示例行是第2行=（4 3 1 2 5），则保存（1 2 3 4 5; 2 3 4; 2），这是（排序的部分路径;有效的断点;索引）。

在对复合记录进行排序后，通过它们查找相邻条目的相等性，直到源索引。例如，（1 2 3 4 5; 2 3 4; 2）和（1 2 3 4 5; 2 3 4; 7）表示来自第7行的部分路由与第2行的路由相同。每次找到副本时，将其对应的原始第一行条目设置为无效点号，例如N + 1。因此，在排序后，使用O（X log X）计算O（X）时间来检测重复项。然后使用O（X）时间通过检查原始行删除具有无效第一个元素的行来挤出重复项。一个稍微更准确的总体成本是O（（M + N）* X * log X），它超过理论最小值O（（M + N）* X）一个对数X因子。如果将复合记录存储在散列表中而不是排序它们，则可以摆脱日志X因子，并在发生重复散列项时将记录标记为删除。