如何在矩阵中查找唯一直线的数量

Question

我们已经给出了大小为M*N的矩阵,并且矩阵的每个位置内的值被表示为点.我们必须找到可以通过2个或更多点绘制的独特直线的数量.例如,M = 2,N = 2

*   *

*   *

可绘制的唯一行数为6.

类似地,如M = 2,N = 3

*    *    *

*    *    *

可绘制的唯一行数为11.

我无法找到解决此问题的方法.请帮忙.

Answer 1

我想既然这样的问题在谷歌上找不到，那么值得回答。这当然是一个有趣的问题，但下次尝试自己提供一些代码。

这是我的解决方案（原谅我的蟒蛇有点生疏）

def notDiagonal(path):
    point1, point2 = path
    a1, a2 = point1
    b1, b2 = point2
    if(a1 == b1):
        return True
    if(a2 == b2):
        return True
    else:
        return False

N, M = 4, 2
matPoints, matPairs, bounds, edges = [], [], [], [(0,0),(N-1,0),(0,M-1),(N-1,M-1)]

def oneEdge(path):
    point1, point2 = path
    if (point1 not in edges and point2 not in edges) or (point1 in edges and point2 in edges):
        return False
    return True

for i in range(N):
    if (i,0) not in bounds:
        bounds.append((i,0))
    if (i,M-1) not in bounds:
        bounds.append((i,M-1))
    for j in range(M):
        matPoints.append((i, j))

for j in range(M):
    if (0,j) not in bounds:
        bounds.append((0,j))
    if (N-1,j) not in bounds:
        bounds.append((N-1,j))        

print("number of points is: ", len(matPoints))

for i in range(len(matPoints)-1):
    for j in range(i+1, len(matPoints)):
        matPairs.append(  ( matPoints[i], matPoints[j]  )   )
matPairCopy = list(matPairs)

print("number of lines before removal: ", len(matPairs))

for i in range(len(matPairs)):

    a = (matPairs[i][0][0] + matPairs[i][1][0])/2.0
    b = (matPairs[i][0][1] + matPairs[i][1][1])/2.0

    if(int(a) == a and int(b) == b):

            # Center point is (int(a), int(b))
            # Delete the partitioned lines if they exist (they may have been deleted before)

            if(  ((matPairs[i][0][0], matPairs[i][0][1]),   (int(a), int(b))) in matPairCopy):
                matPairCopy.remove(   ((matPairs[i][0][0], matPairs[i][0][1]),   (int(a), int(b)))    )
            if(  ((int(a), int(b))  ,  (matPairs[i][1][0], matPairs[i][1][1])   ) in matPairCopy     ):
                matPairCopy.remove(   ((int(a), int(b))  ,  (matPairs[i][1][0], matPairs[i][1][1])   ))

for k in matPairs:
    if(k[0] not in bounds or k[1] not in bounds):
        if(k in matPairCopy):
            matPairCopy.remove(k)
    elif(notDiagonal(k) and (oneEdge(k)) and k in matPairCopy):
                matPairCopy.remove(k)

print("number of lines after removing partitions: ",  len(matPairCopy))

编辑：修复了小问题

N = 2，M = 2：输出 = 6

N = 2，M = 3：输出 = 11

N = 2，M = 4：输出 = 18

N = 3，M = 3：输出 = 20

N = 3，M = 4：输出 = 31

Answer 2

这是一种解决方案，但在性能测量方面不一定是好的解决方案：

列出所有点对(M*N choose 2)，并为每一对(a, b)检查是否有任何其他点c位于同一行。如果是，请从列表中删除(a, c)和。(b, c)

您将剩下由成对点表示的所有独特线条。