如何在矩阵中找到唯一直线的个数

Question

我们得到了一个大小为M*N的矩阵，矩阵中每个位置的值都表示为一个点。我们必须找到可以通过两个或更多点绘制的唯一直线的数量。例如M=2、N=2

*   *

*   *

可以绘制的唯一线条数为6。

与M=2类似，N=3

*    *    *

*    *    *

可以绘制的唯一线条数为11。

我找不到解决此problem.Please帮助的方法。

Answer 1

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

这是我的解决方案(请原谅我的python有点生疏)

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< 2和/或N<2的退化情况。出于测试目的，我能够从在线整数序列百科全书中重现this序列的前10个条目。

这是我的观点:计算水平和垂直的数量是微不足道的，所以专注于其他的斜坡。具有(严格)正斜率的直线和具有(严格)负斜率的直线之间存在1-1对应关系，因此计算正斜率并乘以2。为了计算具有正斜率的直线，我列举了a/b相对质数的所有可能性a /b(因此斜率以简化形式出现)。对于该斜率的每一条线，我将其控制框称为高度a和宽度b的矩形，其属性是它不能在保留在网格中的同时增长到尺寸为2*a x 2*b的矩形，同时保持相同的左下角。在下面这个不太理想的图表中，这条线是斜率1的一个，它通过3个点。控制框将是它在顶行对角切开的正方形，而不是它在底行切开的正方形：

*   *   *   *
      /
*   *   *   *
  /     
*   *   *   *

对于给定的a，b，我通过计算放置轴(第一个维度是高度)框的方式的总数减去放置这样的框的方式的数量来计算给定a，b的控制框的数量，这些框距离网格的右上角足够远，以至于它们有增长的空间。经过一些代数运算(和大量的调试)，我得到了以下Python 3代码：

from fractions import gcd

def distinctLines(m,n):
    if m == 0 or n == 0:
        return 0
    elif m == 1 and n == 1:
        return 0
    elif m == 1 or n ==1:
        return 1
    else:
        numLines = m + n
        slopes = ((a,b) for a in range(1,m) for b in range(1,n) if gcd(a,b) == 1)
        for a,b in slopes:
            numLines += 2*((m-a)*(n-b) - max(m-2*a,0)*max(n-2*b,0))
        return numLines    

示例输出：

>>> for n in range(10): print(distinctLines(3,n), end = ' ')

0 1 11 20 35 52 75 100 131 164 

Answer 3

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

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

剩下的就是由成对的点表示的所有独特的线。