Meine Lineare Algebra kenntnisse sind schon sehr eingerostet, aber ich glaube für folgendes Problem gibt es eine einfache Lösung:

"Gegebene zwei Matrizen, Prüfe ob die eine durch eine Permutation der Zeilen (Spalten) in die andere überführbar ist."

Man könnte nun sicherlich aller Permutationen durchgehen, aber da muss es doch eine einfache hinreichende Bedingung geben …

für Hilfe sehr dangbar, chris

wie groß sind denn die Matrizen? dein menschliches Auge wird ein paar Zeilen doch wohl überblicken können,
ein Computer nimmt eine Map ;)

Naja die können schon sehr groß werden (paar hundert bis tausend Zeilen)

Naja die können schon sehr groß werden (paar hundert bis tausend Zeilen)

Was Slater vorgeschlagen hat (zu jeder Matrix eine Map, in der du zu jedem Tupel
speicherst, wie oft es als Zeile vorkommt und dann die Maps vergleichen) geht nicht?
Das dürfte grob geschätzt in n*log n laufen, wenn die Einträge nicht zu groß sind.

Wenn die Matrizen invertierbar sind, könntest du [latex]C:=A^{-1}B[/latex] ausrechnen,
prüfen, ob im Ergebnis in jeder Zeile nur eine 1 und sonst Null stehen und ob det C
ungleich 0 ist. Aber das ist vermutlich deutlich aufwendiger als obige Methode.

ich schlug vor, in der Map die Zeilen von Matrix A zu speichern (mit halbwegs sinnvollen Hashwert)

für jede Zeile von Maxtrix B dann Hashwert ausrechen, die hoffentlich wenigen Zeilen in der Map finden
und für diese per Hand vergleichen

also ganz normal wie man zwei Mengen beliebiger Objekte vergleicht

edit: sind ja keine Mengen sondern Listen, also durchaus auch noch die Anzahl je Zeile berücksichtigen

Danke für Antworten! Hab gemerkt das ich mein Problem falsch formuliert hatte … hat sich aber jetzt erledigt!

Auch wenns jetzt nicht mehr hilft:

Einfach die Matrizen in je ein Array/Liste umwandeln wo die Zeilen mit nem sinnvollen Hash als Zahl stehen.
Beide sortieren und vergleichen. O(n*log(n))
Wofür brauche ich eine Map? ;)

- eth

um das Sortieren gar zweimal zu sparen