确定一个矩阵的一些行置换是托普利兹 [英] Determine if some row permutation of a matrix is Toeplitz

问题描述

一个托普利茨矩阵是一个矩阵，其中每个对角线下降，从左至右是不变的。给出一个二进制矩阵M，是否有一个有效的算法，以确定是否有行的置换，这使得它的Toeplitz？

A Toeplitz matrix "is a matrix in which each descending diagonal from left to right is constant." Given a binary matrix M, is there an efficient algorithm to determine if there is a permutation of the rows which makes it Toeplitz?

例如，设置

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

如果你交换第一排和第二排，你得到

If you swap the first and second row you get

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

这是托普利茨。

which is Toeplitz.

在Python中，你可以做一个随机二进制矩阵如下：

In python you can make a random binary matrix as follows.

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

我想测试适用于M。

I would like to apply the test to M.

（注矩阵M不必是正方形。）

(Note the matrix M does not need to be square.)

推荐答案

这个问题可以在线O（高*宽）的时间，其中<​​code> ^ h 的数量来解决行是W 是列数。

This problem can be solved in linear O(h*w) time, where h is number of rows and w is number of columns.

构造的曲线图，其中每个顶点对应于（W-1） -length子，其可以是preFIX或在基质中的一些行的后缀。一个顶点可以对应于几个重复的子串。连接这些顶点与 ^ h 边缘。每个边缘对应于行的矩阵。它是从对应于该行的preFIX到对应于该行的后缀的顶点的顶点指向

Construct a graph where each vertex corresponds to (w-1)-length substring which may be either prefix or suffix of some row in the matrix. One vertex may correspond to several duplicate substrings. Connect these vertexes with h edges. Each edge corresponds to row of the matrix. It is directed from the vertex corresponding to this row's prefix to the vertex corresponding to this row's suffix.

要确定是否某些行置换是托普利兹矩阵，它是足够检查构造图是欧拉图。为了找到频带排列本身，就足以找到一笔画问题在该图中。

To determine if some row permutation is a Toeplitz matrix, it is enough to check if constructed graph is Eulerian graph. To find permutation itself, it is enough to find Eulerian path in this graph.

我们需要互连顶点和边一些有效的方式。简单的方法假设比较各行的子字符串对。这是因为r不是很有趣（H ² * w）的时间复杂度。

We need some efficient way to interconnect vertexes and edges. Straightforward approach assumes comparing each row-substring pair. This is not very interesting because of O(h²*w) time complexity.

建筑广义后缀树（或后缀数组）为矩阵的行只需要O（高*宽）时间。而这棵树允许互连的顶点和边也以线性时间：深度每个内部节点 W-1 重presents一些（W- 1） - 长度字符串（顶点）;每个叶片连接到这个节点重新presents一些行的后缀（引入边）;和连接到该节点的孩子每个叶重presents含有该字符串为preFIX（流出边）某行。

Building Generalized suffix tree (or suffix array) for rows of the matrix needs only O(h*w) time. And this tree allows to interconnect vertexes and edges also in linear time: each internal node with depth w-1 represents some (w-1)-length substring (vertex); each leaf attached to this node represents some row's suffix (incoming edge); and each leaf attached to this node's children represents some row containing this substring as a prefix (outgoing edge).

另一种方法是使用哈希映射。随着（W-1） - 长度矩阵行的子字符串作为密钥，对排索引列表（对于行，其中此子是preFIX /后缀）作为一个值。相较于后缀树/阵列的方法，这使得简单的实现，需要较少的内存（每个按键的需求只为哈希值，并指向字符串的开头空格），应加快工作速度（平均），但具有较差的最坏情况的复杂性： Ø（H ² * W）。

Other alternative is to use hash map. With (w-1)-length substring of matrix row as a key and pair of lists of row indexes (for rows where this substring is prefix/suffix) as a value. Comparing to suffix tree/array approach, this allows simpler implementation, needs less memory (each key needs only space for hash value and pointer to beginning of the substring), should work faster (on average), but has inferior worst-case complexity: O(h²*w).

这篇关于确定一个矩阵的一些行置换是托普利兹的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！