确定矩阵的某些行排列是否为Toeplitz

Question

甲托普利兹矩阵"是一个矩阵,其中每个对角降序从左至右是恒定的." 给定二进制矩阵M,是否有一种有效的算法来确定是否存在使其成为Toeplitz的行的排列？

例如,设置

M= [0 1 1]
   [1 1 0]
   [1 0 1]

如果你交换了第一行和第二行

[1 1 0]
[0 1 1]
[1 0 1]

这是Toeplitz.

在python中,您可以创建一个随机二进制矩阵,如下所示.

n = 10
h = 10
M =  np.random.randint(2, size=(h,n))

我想将测试应用于M.

(注意矩阵M不需要是正方形.)

Answer 1

这个问题可以在线性O(h*w)时间内解决,其中h行w数是列数.

构造一个图形,其中每个顶点对应于(w-1)-length子字符串,该子字符串可以是矩阵中某行的前缀或后缀.一个顶点可以对应于几个重复的子串.将这些顶点与h边连接起来.每个边缘对应于矩阵的行.它从对应于该行前缀的顶点指向对应于该行后缀的顶点.

要确定某些行排列是否是Toeplitz矩阵,检查构造的图是否为欧拉图就足够了.要找到排列本身,在此图中找到欧拉路径就足够了.

我们需要一些有效的方法来互连顶点和边缘.直接的方法假设比较每个行 - 子串对.由于O(h ²*w)时间复杂度,这不是很有趣.

构建矩阵行的通用后缀树(或后缀数组)仅需要O(h*w)时间.并且这个树允许在线性时间内互连顶点和边缘:每个具有深度的内部节点w-1代表一些(w-1)长度子串(顶点); 附加到此节点的每个叶子代表一些行的后缀(传入边缘); 并且附加到此节点的子节点的每个叶子表示包含此子字符串的某一行作为前缀(传出边缘).

其他替代方法是使用哈希映射.与(w-1)矩阵的行的子-length作为密钥和对行索引的列表(对于行,其中该子串是前缀/后缀)作为值.与后缀树/数组方法相比,这允许更简单的实现,需要更少的内存(每个键只需要空间用于散列值和指向子串的开头),应该更快(平均)工作,但具有较差的最坏情况复杂性: O(h ²*w).