python - 在二进制数组中查找直角三角形坐标

Question

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

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 索引]。

---

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

---

我的第一个想法是使用行和列的总和。那些行总和 >= 2 的行值得探索，然后使用列总和 >=2。那么您将需要一种有效的方法来找到交叉点。我会对使用此方法或任何其他可能更好更快的方法的函数感兴趣。

{例如或者，您可以从图论的角度考虑这个问题。行和列将是二分图的节点[行是一组，列是另一组]。那么这里显示的矩阵将是完整二部图的邻接矩阵的一个象限。换句话说，它只是行集和列集之间的交叉项的一部分，因为集内部分将全部为 0，因为行节点不连接到其他行节点；仅适用于列节点。从这个角度来看，直角三角形在二分图上看起来就像一条长度为 3 的路径。我认为矩阵方法更简单，但我对这里的任何算法都持开放态度。

Answer 1

是的，我相信你想多了。生成行和列总和，并检查每个数组位置是否存在交集。

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

# 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.