Vergleich von Array innerhalb eines Array anhand eines Teiles des Arrays

[dadie]

Erstmal möchte ich kurz sagen das ich keinen Programm-Code Requestiere sondern eher eine Idee brauche wie ich diese Aufgabe effektiver Lösen könnte.

Die Idee ist bislang das ich eine "Matrix" Baue über Array. Also erstmal besteht das erste Array aus der Anzahl der X-Werte und in jedem Array mit X-Werten sind die die entsprechenden Y-Werte.

Im Grunde habe ich also quasi so einen Aufbau:

Code:

2 2 2 2 2 1
2 1 2 2 2 1
1 1 1 3 2 3
1 1 3 3 2 1

Nun habe ich einen kleineren Array der im Grunde so aussieht:

Code:

3 2
1 3

Nun möchte ich herausfinden Ob diese Array-Formation vorhanden ist. Und falls ja bei welchen X-Y-Werten.

Aktuell löse ich das Problem in dem ich über Determinanten-Rechnung bzw. ab 4x4 Matrix-Rechnung das Ergebnis errechne das gleiche dann ebenfalls für alle Blöcke innerhalb des Arrays tue und dann vergleiche welche Ergebnisse gleich sind.

Nun sei mir verziehen fühlt es sich an wie ein Work-Around aber weniger wie eine echte Lösung. Daher einfach mal die Frage ob mein Gefühl richtig ist oder ob das wirklich der richtige Weg ist.

[R.D.]

Du willst also in deiner Matrix ein bestimmtes Muster herraus filtern? Sehe ich das so richtig?

Edit:
Ist der Array immer gerade? also hat er immer eine gerade Anzahl an Elemente?

[dadie]

Du willst also in deiner Matrix ein bestimmtes Muster herraus filtern? Sehe ich das so richtig?

Edit:
Ist der Array immer gerade? also hat er immer eine gerade Anzahl an Elemente?

...

Ja im Grunde ja. Ich möchte nur wissen OB das Muster vorhanden ist. Wenn ja wie oft. Und ebenfalls bei welchen "X" und "Y" werten. Wobei der "X" Wert der Index des Haupt Array darstellt und der "Y" Wert der Array innerhalb des Arrays.

Die Größe des Gesamt-Arrays und Vergleichs-Arrays kann auch ungerade sein. Wobei das Vergleichs-Array per Definition immer kleiner ist.


Es muss auch nicht über Arrays gelöst werden. Da ich das Problem Mathematisch angehe dachte ich mir nur das so eine Matrix doch Ordentlicher und einfach wäre.

[nudelsalat]

Du kannst dir mal den Boyer-Moore Suchalgorithmus anschaun und versuchen für deine Aufgabe zu adaptieren:
http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus

[Jesus_666]

Mein erster Gedanke dabei ist: Reguläre Ausdrücke. Regexps lösen das genau gleiche Problem, nur in einem anderen Kontext. Man kann vielleicht dein Problem auf diesen Kontext abbilden (in welchem Fall ein Regexp es lösen kann) oder aber sich ansehen, wie Regexp-Bibliotheken wie PCRE die Eusdrücke evaluieren und dazu ein Analogon bauen.

Ich empfehle dir, dir mal String-Suchalgorithmen anzusehen; einige der Kniffe da kannst du übernehmen Beispielsweise könnte der Boyer-Moore-Algorithmus dir erlauben, die Suchzeit deutlich einzuschränken. Das ist auch der Grund, warum ich eine Suche mit direktem Vergleich der Zellwerte einer mit Vergleich der Determinanten vorziehe.

Fangen wir mal mit einem einfachen Algorithmus (tatsächlich dem naiven) an:

Code:

Sei haystack die Matrix, in der gesucht wird.
Sei needle die Matrix, nach der wir suchen.
Sei matches eine Liste von der Positionen, an denen Treffer gefunden wurden
  (implementiert als Liste von Paaren von Ganzzahlen).

FOR y_start IN [0 .. (haystack.höhe - needle.höhe)]
    FOR x_start IN [0 .. (haystack.breite - needle.breite)]
        FOR y IN [0 .. needle.höhe - 1]
            FOR x IN [0 .. needle.breite - 1]
                IF haystack[y_start + y][x_start + x] != needle[y][x]
                THEN GOTO :weiter
        matches.add(<y, x>)
        :weiter
RETURN matches

Der ist mit O(n⁴) wirklich langsam, aber es ist schon mal ein Anfang. Wenn wir uns jetzt den Boyer-Moore ansehen, dann haben wir zwei Heuristiken, die uns erlauben, bei Fehlern Teile der Matrix zu überspringen. Ich sehe gerade, daß ich keine Zeit mehr habe, das jetzt konkret zu erarbeiten, aber wenn man das Suchfenster anhand dieser Regeln zumindest auf der X-Achse verschiebt, kann man einiges an Aufwand einsparen.

Es müßte möglich sein, sich zu erarbeiten, ob man auch gleich mehrere Y-Zeilen überspringen kann, was natürlich den Aufwand deutlich senkt. Auch dafür habe ich jetzt leider keine Zeit mehr.

Auf jeden Fall kannst du vermeiden, für jede der (haystack.breite - needle.breite)*(haystack.höhe - needle.höhe) möglichen Positionen Vergleiche durchführen zu müssen.


PS: Verdammt, von nudel geninjat.

[dadie]

Heureka

Die Lösungs-Ideen sind gar nicht mal schlecht. Ich wollte unbedingt das ganze Zwei-Dimensional vergleichen. Aber wenn ich es erst einmal Ein-Dimensional überprüfe geht es wirklich einfacher. 666 sei aber beruhigt. Deine Beitrag hat mir ebenfalls einen Denk Anstoß gegeben ^^

[R.D.]

Ah verdammt Warum muss ich auch fernseh gucken. Boyer-Moore hätte ich auch gesagt (Aber nur, weil ich das erst vor kurzem gelernt habe xD)

@Jeez
Du springst! D: