Herzlichen Glückwunsch an Helmut !
Davids Lösung hat einen Moment gedauert nachzuvollziehen, und da David noch keine Zeit gefunden hat, seine Lösung zu erläutern, versuche ich einfach mal die Neugierigen zu erhellen.
Der Algorithmus geht alle Elemente des Quadrats rückwärts durch (i ist der Index des aktuellen Elements).
Für jedes Element wird dann die Anzahl der Vorkommen dieses Elements in den vorangegangenen Zeilen gezählt. Das wird dadurch bewerkstelligt, das j durch die Initialisierung in der Laufbedingung auf das erste Element der aktuellen Zeile (also derjenigen, in der sich i befindet) gesetzt wird.
Durch die Dekrementierung in der Laufbedingung der inneren while-Schleife läuft j also vom letzten Element der vorangehenden Zeile bis 0.
Wird das aktuelle Element in den vorangegangenen Zeilen gefunden, wird der Zähler num_equals_left dekrementiert, der zu Beginn mit der für ein lateinisches Quadrat erwarteten Anzahl an Übereinstimmungen initialisiert wurde.
Allerdings stecken hier zwei Tricks im Detail: der Zähler wurde mit der doppelten Anzahl der erwarteten Übereinstimmungen initialisiert, da die doppelte Anzahl mit weniger Token berechnet werden kann (spart /2), daher wird der Zähler immer um 2 verringert.
Zum anderen wird im Falle einer Übereinstimmung in der selben Zeile, die ja in einem lateinischen Quadrat nicht vorkommen darf, der Zähler um 1000 verringert, einfach um das Ergebnis der Zählung unabhängig von den übrigen Vergleichen in jedem Fall ungleich 0 werden zu lassen (erspart ein if(i % size == j % size) return false).
Bleibt die Frage, welche Anzahl an Übereinstimmungen wir für ein lateinisches Quadrat erwarten können. Alle size Elemente einer Zeile müssen in allen vorangegangenen Zeilen je einmal auftauchen.
Für die lezte Zeile erwarten wir also size*(size-1) Übereinstimmungen. Für die vorletzte Zeile, die ja ebenfalls size Elemente beinhaltet, aber eine Zeile weniger vor sich hat: size*(size-2). Das setzt sich fort bis zur ersten Zeile, die keine vorangehenden Zeilen mehr hat: size*0.
Faktor size ausklammern liefert: size*[(size-1) + (size-2) + ... + 1 + 0]
Die eckige Klammer entspricht der arithmetischen Reihe: die Summe aller Zahlen von 1 bis n ist (n*(n+1))/2, size-1 für n einsetzten: ((size-1)*size)/2, und das in die obige Gleichung eingesetzt liefert eine erwartete Anzahl an Übereinstimmungen in einem lateinischen Quadrat von (size*size*(size-1))/2 = (size^3 - size^2)/2
Auf die halbierung kann - wie bereits oben erwähnt - verzichtet werden, wenn immer doppelt gezählt wird.
Und warum funktioniert das Ganze nur für lateinische Quadrate ? Folgende Überlegungen machen es plausibel (den formalen Beweis überlasse ich David :p ):
1. Wenn mehr als n Symbole verwendet werden, existieren folglich weniger Übereinstimmungen
2. Wenn ein Symbol mehrfach in einer Spalte auftritt, wird die Summe durch -1000 "abgeschossen", die Summe kann nicht mehr 0 und damit das Ergebnis nicht mehr true werden
3. Wenn ein Symbol in einer Zeile mehrfach vorkommt, wird dieses von den vorangegangenen Zeilen gezählt. Darüber hinaus werden die Vorkommen dieses Symbols in den folgenden Zeilen doppelt gezählt, allerdings wird dadurch ein anderes Symbol in den folgenden Zeilen gar nicht gezählt, dieser Teil des Fehlers gleicht sich also potentiell wieder aus.
Ich hoffe, der Ansatz ist klar geworden. Ich ziehe den Hut vor David, für diese Lösung ! Respekt !
19.04.2024, 20:02
Zum Seitenanfang
