在二进制数组中查找直角三角形坐标 [英] Finding right triangle coordinates in binary array

问题描述

说我有一个MxN二进制矩阵.它不一定是稀疏的.我对查找数组中所有直角三角形的顶点的坐标感兴趣.直角三角形的意思是:假设矩阵中的1或True值是三角形的顶点，而0或False元素为空.那么直角三角形是在视觉上形成直角三角形的布置.顶点是指对应于三角形直角的顶点.例如.在以下5x6数组中:

Say I have an MxN binary matrix. It is not necessarily sparse. I'm interested in finding the coordinates of the apexes of all of the right triangles in the array. By right triangle, I mean: pretend that the 1 or True values in the matrix are vertices of triangles, and the 0's or False elements are null. Then a right triangle is an arrangement that visually forms a right triangle. By apex I mean the vertex which corresponds to the right angle of the triangle. E.g. in the following 5x6 array:

0 0 1 0 1 0
0 1 0 0 0 0
1 0 0 1 0 1
0 0 1 0 0 0
0 0 0 0 0 0

只有1个直角三角形.它是顶点为的三角形: (0,2)是顶点，(3,2)是左下角，(0,4)是右上角，我从0开始索引，从左上角开始[Python indexing].

There is only 1 right triangle. It is the triangle with vertices at: (0,2) is the apex, (3,2) is the lower left, (0,4) is the upper right, where I'm indexing from 0, starting at the top left [Python indexing].

对于给定的MxN数组，我想要一个Python函数F(A)，该函数返回子数组L的数组，其中每个子数组都是数组中直角三角形顶点的坐标对.对于数组的相同元素是多个三角形的顶点的情况，最终我只想要唯一的子数组，但是现在该函数可以复制它们.例如，对于上面的数组A，F(A)将返回数组L = [[0,2]]

For a given MxN array, I want a Python function F(A) that returns an array L of subarrays, where each subarray is the coordinate pair of the apex of the right triangles in the array. For the case where the same element of the array is the apex of multiple triangles, ultimately I'll just want unique subarrays, but for now the function can duplicate them. As an example, for the array A above, F(A) would return the array L = [[0,2]]

我的第一个想法是使用行和列的总和.那些行总和> = 2的行值得探讨，然后使用列总和> = 2.然后，您将需要一种有效的方法来找到相交处.我会对使用此方法或任何其他更好或更快速的方法的功能感兴趣.

My first thought would be to use row and column sums. Those rows with a row sum >= 2 are worth exploring, and then use the columns sum >=2. Then you would need an efficient way to find the intersections. I would be interested in a function using this method or any other method which might be better and faster.

{例如作为替代方案，您可以从图论的角度考虑这一点.行和列将是二部图的节点(行将是一组，列将是另一组).这样，此处显示的矩阵将是完整二部图的邻接矩阵的一个象限.换句话说，这将只是行集和列集之间的交叉项的一部分，因为集内的部分将全部为0，因为行节点未连接到其他行节点.仅到列节点.从这个角度来看，直角三角形看起来像二分图中的长度为3的路径.我认为矩阵方法比较简单，但是我可以在这里使用任何算法.}

{E.g. as an alternative, you could think about this from a graph theory perspective. The rows and columns would be nodes of a bipartite graph [the rows would be one set, the columns the other set]. Then the matrix shown here would be one quadrant of the adjacency matrix of the full bipartite graph. In other words, it would be the part of only the cross terms between the row and column sets, since the within set parts would all be 0 since the row nodes don't connect to other row nodes; only to column nodes. From this perspective, a right triangle would look like a path of length 3 on the bipartite graph. I think the matrix approach is simpler, but I'm open to any algorithms here.}

推荐答案

是的，我认为您对此考虑过多.生成行和列的总和，并检查每个数组的位置是否相交.

Yes, I believe that you're over-thinking this. Generate the row and column sums, and check each array location for intersection.

我还没有测试语法，但是会是这样:

I haven't tested the syntax, but it will be something like this:

# Generate row and column sums
row_sums = (sum(A[M]) for M in range(len(A)))
col_sums = (sum([A[M, N] for M in range(len(A))] for N in range len(A[0]))

# Now, check each element in the array for being a vertex
vertices = 
    [(row, col) if A[row, col] and row_sums[row] > 1
                               and col_sums[col] > 1
          for row in range(len(A)) for col in range(len(A[0]))]

# You now have a list of all solutions, with no duplicates.

这篇关于在二进制数组中查找直角三角形坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！