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具有相同的路由，因为存在不同的断点导致部分路由[1], [2 4], [3] and [5]。

我怎么才能干净利落地做这件事呢？矩阵可以包含许多元素，如X = 5e4行和N = 10、M = 6。

Answer 1

对于常数M，N，这可以在O(X log X)时间内解决，方法是将组合记录排序为顺序，然后测试相邻条目的相等性。

我所说的“复合记录”是指将行的函数及其断点组合到单个记录中的记录。对于给定行，可以通过以下方法获得该函数：

1. 将断点应用于行，获取部分路由的列表。
2. 按每个路由的第一个元素将部分路由排序为升序。例如，sort {4，3，1 2，5} as {1 2，3，4，5}。
3. 通过连接已排序的部分路由、有效断点和索引到源行来形成新的复合记录。例如，如果上一步中的示例行是row 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)时间来检测重复项。然后，使用O(X)时间通过遍历原始行来挤出重复项，删除第一个元素无效的行。

稍微精确一点的总体成本是O((M+N)*X*log )，它比理论上最小的O((M+N)*X)超出一个log因子。如果将复合记录存储在哈希表中，而不是对它们进行排序，并在出现重复的哈希项时标记要删除的记录，则可以消除log X因子。