So finden Sie die Anzahl der eindeutigen Geraden in einer Matrix

Question

Wir haben eine Matrix der Größe M * N gegeben und Wert innerhalb jeder Stelle der Matrix wird als ein Punkt dargestellt. Wir müssen eine Anzahl von eindeutigen geraden Linien finden, die durch 2 oder mehr Punkte gezogen werden können. Zum Beispiel M = 2, N = 2

* * 

* * 

Anzahl der einzigartigen Linien gezogen werden können, ist 6.

Ähnlich wie M = 2, N = 3

* * * 

* * * 

Anzahl der einzigartigen Leitungen gezogen werden ist 11.

Ich bin nicht in der Lage, einen Weg zur Lösung dieses Problems herauszufinden.Bitte helfen.

Answer 1

Dies ist eine Lösung, aber nicht unbedingt eine gute Performance-Messungen:

Machen Sie eine Liste aller Paare von Punkten (M*N choose 2) und für jedes Kontroll Paar (a, b) wenn ein anderer Punkt c ist auf der gleichen Linie. Ist dies der Fall, löschen Sie (a, c) und (b, c) aus der Liste.

Sie haben alle eindeutigen Linien, die durch Punktepaare dargestellt werden.

Answer 2

Ich dachte, da eine solche Frage nirgendwo auf Google zu finden ist, war es eine Antwort wert. Es ist sicherlich eine interessante Frage, aber versuchen Sie, beim nächsten Mal ein bisschen Code zu liefern.

Dies ist meine Lösung (Vergib meine Python etwas verrostet sein)

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)) 

edited: Feste kleine Ausgabe

N = 2, M = 2: Output = 6

N = 2, M = 3: Ausgang = 11

N = 2, M = 4: Output = 18

N = 3, M = 3: Output = 20

N = 3, M = 4: Output = 31

Answer 3

Split das Problem in mehrere Teile:

• alle unterschiedlichen Werte finden die Tonhöhe einer Linie halten kann: diese Abstände liegen müssen zwischen (0 , -1) (einschließlich) und (0 , 1) (ausschließlich) auf dem Einheitskreis. Mit Ausnahme von (0 , -1) und (1 , 0) hat jeder Ton (x , y) einen Peer, der als (x , -y) definiert ist und den Anforderungen entspricht. Im Grunde wäre der Satz gültiger Abstände
  {(0,-1),(1,0)} merge D:{da , db|da=(1,y), y=m/n with 0 <= M < M and 0 < n < N , db=(1 , y(db)}. Die einzelnen Tonhöhen zu finden, ist ein bisschen schwierig (ich würde vorschlagen, diesen Teil einfach brutal zu erzwingen).
• finden die Anzahl der Zeilen für jede einzelne Teilung der Linie: die Linie mit Steigung (0 , -1) kann (1 , 0) genau N mal mit Pech genau M mal die Zeile eingefügt werden, für jede andere Zeile folgenden gilt: die Tonhöhe (x , y) sein lassen wobei x und y ganze Zahlen sind. Es gibt N - x + M - y Linien mit dieser Tonhöhe, die mindestens 2 Punkte abdecken. Anforderungen an die Liste der Stellplätze:
  • jedes Element in der Liste ist einzigartig: für einen Pitch p = (x , y) kein Pech b = (u , v) so dass x = d * u und y = d * v.
  • jedes Element in der Liste besteht aus ganzen Zahlen: für jede Steigung p = (x , y), x und y muss für die schreckliche Weise

Leider ganze Zahlen sein, zu erklären, kein Werkzeug einer generieren finden konnten, mathematische Notation.

Answer 4

Wenn Sie eine Brute-Force-Lösung wollen here ist eine Python-Implementierung. Grundsätzlich durchläuft es alle Punktepaare und behält nur in normaler Form eindeutige Linien bei. Nachfolgend finden Sie eine Beispielausgabe

M = 1 N = 1 Count = 0 
M = 1 N = 2 Count = 1 
M = 1 N = 3 Count = 1 
M = 1 N = 4 Count = 1 
M = 1 N = 5 Count = 1 
M = 1 N = 6 Count = 1 
M = 1 N = 7 Count = 1 
M = 1 N = 8 Count = 1 
M = 1 N = 9 Count = 1 
M = 2 N = 2 Count = 6 
M = 2 N = 3 Count = 11 
M = 2 N = 4 Count = 18 
M = 2 N = 5 Count = 27 
M = 2 N = 6 Count = 38 
M = 2 N = 7 Count = 51 
M = 2 N = 8 Count = 66 
M = 2 N = 9 Count = 83 
M = 3 N = 3 Count = 20 
M = 3 N = 4 Count = 35 
M = 3 N = 5 Count = 52 
M = 3 N = 6 Count = 75 
M = 3 N = 7 Count = 100 
M = 3 N = 8 Count = 131 
M = 3 N = 9 Count = 164 
M = 4 N = 4 Count = 63 
M = 4 N = 5 Count = 96 
M = 4 N = 6 Count = 141 
M = 4 N = 7 Count = 188 
M = 4 N = 8 Count = 246 
M = 4 N = 9 Count = 309 
M = 5 N = 5 Count = 145 
M = 5 N = 6 Count = 214 
M = 5 N = 7 Count = 282 
M = 5 N = 8 Count = 371 
M = 5 N = 9 Count = 466 
M = 6 N = 6 Count = 314 
M = 6 N = 7 Count = 415 
M = 6 N = 8 Count = 546 
M = 6 N = 9 Count = 687 
M = 7 N = 7 Count = 548 
M = 7 N = 8 Count = 723 
M = 7 N = 9 Count = 910 
M = 8 N = 8 Count = 954 
M = 8 N = 9 Count = 1201 
M = 9 N = 9 Count = 1512 

alternativer Ansatz

Wie wäre eine Variante der Hough Transform verwenden, die Linien erkennt. Üblicherweise verwendet die Hough-Transformation einen Akkumulator, um Linien in Fächer ihres Radius und Winkels zu gruppieren. Für ein festes M und N können Sie jedoch die kleinste Auflösung sowohl in der Radius- als auch in der Winkelrichtung bestimmen, so dass Sie eine genaue Antwort erhalten.

Berechnen Sie zum Beispiel die Menge aller Linienradien und Winkel aller Punkte, indem Sie den oberen linken Punkt als Ursprung verwenden. Diese Werte sollten für alle anderen Punkte gleich sein. Sie müssen jedoch auch die entsprechenden Winkel in die anderen drei Quadranten aufnehmen.

Führen Sie dann die Hough-Transformation mit diesen Werten für Ihre Akkumulatorfachzentren aus. Die Behältergröße muss die kleinste Auflösung in den oben berechneten Werten sein. Jedes Akkumulatorfach mit einer Anzahl von mehr als eins stellt eine Linie dar, die mehr als einen Punkt durchläuft. Addiere sie und das ist deine Antwort.

Answer 5

Auf edit: habe ich einige Codes degeneriert Fälle zu behandeln, in denen M < 2 und/oder N < 2. Für Testzwecke, konnte ich die ersten 10 Einträge von this Sequenz aus der On-line Encyclopedia of Integer reproduzieren Sequenzen.

Hier ist meine Meinung: Es ist trivial, die Anzahl der horizontalen und vertikalen zu zählen, also konzentrieren Sie sich auf die anderen Steigungen. Es gibt eine 1: 1-Entsprechung zwischen (streng) positiven und (streng) negativen Linien, also zähle die positiven und multipliziere mit 2. Um die Linien mit positiver Steigung zu zählen, zähle ich alle Möglichkeiten a/b mit a, b relativ prim (so ist die Steigung in reduzierter Form). Für jede Linie dieser Steigung rufe ich ihr Kontrollfeld das Rechteck der Höhe a und der Breite b mit der Eigenschaft an, dass es zu einem Rechteck der Dimensionen 2 * ax 2 * b mit der gleichen unteren linken Ecke nicht wachsen kann, während es bleibt das Gitter. Im folgenden nicht ganz optimalen Diagramm ist die Linie eine von Steigung 1. Sie verläuft durch 3 Punkte.Die Steuerbox wäre der Platz es in der oberen Reihe durch diagonal schneidet eher als das Quadrat schneidet sie in der unteren Reihe durch:

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

ich die Anzahl der Kontrollkästchen für einen gegebenen a zählen, b durch das Zählen Gesamtzahl der Möglichkeiten, ein Axb-Feld (erste Dimension ist Höhe) zu platzieren, minus der Anzahl der Möglichkeiten, eine solche Box so weit zu platzieren, dass sie weit genug von der oberen rechten Ecke des Gitters entfernt sind, wo sie Platz zum Wachsen haben. Nach einem wenig Algebra (und einer Menge Debugging) kam ich mit dem folgenden Python 3-Code auf:

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  

Beispielausgabe:

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

0 1 11 20 35 52 75 100 131 164 

Answer 6

Zusätzlich zu den anderen Antworten oben:

Dies ist der Gegenstand der Veröffentlichung On lines and their intersection points in a rectangular grid of points von Seppo Mustonen. Ich fand dies, indem ich John Coleman 's Ausgang 0 1 11 20 35 52 75 100 131 164 in der On-Line Encyclopedia of Integer Sequenzen nachschlagen, die mich auf Sequenz A160843 zeigte.