Permutationen...

Hallo Leute,

ich fühle mich gerade etwas dämlich.

Ich habe zwei Mengen A und B (B ist mächtiger als A). Ich möchte nun alle Kombinationen durchgehen, wie man den Elementen aus A jeweils ein Element aus B zuordnen kann, wobei jedes Element aus B nur maximal einmal als Ziel einer Zuordnung dienen soll, in jeder beliebigen Kombination (Ziehen ohne zurücklegen?).

Ich suche nun einen Algorithmus, der mir möglichst einfach diese Kombinationen "aufzählt" und sie auch sukzessive aufbaut, so dass ich ganze Teil-Permutationen frühzeitig rausschmeißen kann. Also irgendwie so: wähle irgendwie eine Zuordnung für das erste Element aus A, wenn ein bestimmter Test nicht fehlschlägt, wähle ein Zuordnung für das nächste Element aus A, mache wieder den Test usw..

Im Moment fallen mir nur Ansätze ein, die dieses "Ziehen" aus der Menge der übrigen Elemente 1:1 umsetzen, aber damit ist ja immer eine Suche und Entfernen aus Containern verbunden. Da gibt es doch bestimm was schlaueres?

Viele Grüße,
Deci

Hrmmm, nach etwas Überlegung komme ich zum Schluss, dass es vielleicht klüger wäre, erstmal alle a aus A gegen alle b aus B zu testen und mir zu merken, wo der Test erfolgreich ist. Danach müsste ich bloß noch aus diesen Daten eine Belegung raussuchen, die kein b aus B mehrfach zuordnet... Am Ende bin ich nur an irgendeiner gültigen Belegung interessiert, nicht an allen.

Edit: Stimmt auch nicht, ich brauche potentiell alle gültigen Belegungen... Also stünde ich dann vor dem Problem, aus den x Erfolgslisten diejenigen zu basteln, in denen alle Elemente verschieden sind... Hrmmhrmmm

hallooooohoooohh!!!

hrmmhhmrm ?!
lol!

... wenn ein bestimmter test nicht fehlschlägt ...

bist du etwa über die erstaunliche anzahl der antworten erstaunt, wenn du
dir in rätseln etwas in den bart murmelst?

also, ein paar infos wären schon nicht schlecht.
ansonsten, falls sich jedes a einem b bedingungslos zuordnen lässt dürfte das
nicht allzu schwer zu programmieren gehen ...

Michael E.

Am wenigsten Arbeit hast du so: Gehe mit http://www.cplusplus.com/reference/algorithm/next_permutation/ alle Permutationen von B durch. Weise dann stets dem i-ten Element aus A das i-te Element der Permutation von B zu. ~~Das ist laufzeitoptimal, falls die Kardinalität von B in der Größenordnung der Kardinalität von A liegt.~~ Das ist laufzeitoptimal, wenn B genauso groß ist wie A. Ansonsten gibts schnellere Algorithmen. Ist B viel größer als A?

Vielen Dank, auch für die etwas unfreundliche Antwort. Ich war halt während meiner Fragestellung noch sehr auf einen Lösungsweg meines Problems versteift.
Ich denke ich komme lieber mal mit dem ganzen Problem.

Ich habe einen algebraischen AST und möchte darin ein Muster-AST matchen. Ohne Umformungen ist das ja ziemlich einfach, aber in diesem Fall mache ich mir Gedanken darüber, auch die Kommutativität und Assoziativität der Operationen ausnutzen. Das werden natürlich schnell extrem viele Kombinationen. Ich habe über verschiedene Herangensweisen nachgedacht.

Ich forme den binären AST in einen n-ären um (Ich stampfe sozusagen alle Teilbäume mit gleicher Operation zusammen). Beim Matchen gehe ich Depth-First vor, wobei jeder Teilvergleich dafür zuständig ist, den Rest des Gesamtvergleichs anzustoßen, so dass ich an Ort und Stelle alle Permutationen der kommutativen oder assoziativen Operatoren durchgehen kann. Dann gibt es noch zwei Unterteilungen:

1a) Ich erlaube es irgendwie, dass nur Teile eines n-ären Baums gematcht werden.
1b) Es muss ein "Wildcard" im Muster sein, dass alle ungematchten Teile "absorbiert".

Ich versuche irgendwie, das Muster über den Problembaum zu "strecken" oder zu "verzerren". Sagen wir, ich habe ein Wildcard im Muster, ich lege dafür irgendeine Position im AST fest und ziehe das Muster entsprechend in die "Länge" oder vertausche gegebenenfalls die Kinder bestimmter Knoten. Wenn ich ein Wildcard in solcher weise "festgepinnt" habe auf dem Problembaum, dann schaue ich, ob das Wildcard nochmal im Muster vorkommt und verzerre den dazugehörigen Unterbaum so, dass das beide Wildcards "passen" (Dafür kann es natürlich mehrere Möglichkeiten geben). So stelle ich mir vor, schneller unnütze Matchversuche auszuschließen. Aber das ist natürlich noch lange kein funktionierender Algorithmus. Auch gibt es so keine "Rotationen", welche zu einem gültigen Match führen könnten (Also die Suche ist nicht "komplett").
Ich benutze das Zusammenstampfen aus 1), benutze "einfache" Matches und Transformationen um auf eine Normalform zu kommen und dann dedizierte Algorithmen, um diese Normalformen umzuformen oder zu vereinfachen.

Gibt für soetwas schon einen funktionierenden, "effizienten" (also soweit es halt geht, es gibt halt schnell irre viele Kombinationen) Algorithmus? Ich glaube ich bräuchte doch einiges an Überlegungszeit um da etwas brauchbares auszustoßen.

Ich bin auf meiner Internetrecherche auf Papers über AC(I)-Probleme gestoßen und meine, darin irgendwie meine Problemstellung erkannt zu haben. Aber die waren natürlich ziemlich theoretisch gehalten und in diese Theorie müsste ich mich erst hereinarbeiten, um darüber eine Aussage treffen zu können.

Viele Grüße,
Deci

Jester

Wenn Du Assoziativität ausnutzen willst, solltest Du auf jeden Fall den binären Baum zusammenfassen, sodass Du Operatoren mit mehr Kindern hast. Das beseitigt ja letztlich genau das Teilproblem, dass man eben auf so viele verschiedene Arten klammern kann. Danach kommts jetzt drauf an.

Mein generelles Suchwort wäre "Subtree Isomorphism". Aber das ist vermutlich nur die halbe Wahrheit. Zum einen sind Deine Knoten wahrscheinlich gelabelt, also Labeled Subtree Isomorphism. Wenn Deine Operatoren nicht kommutativ sind (oder du das nicht ausnutzen willst), dann solltest du noch ordered dazupacken. Und zuguterletzt willst du wahrscheinlich garnicht beliebige Teilbäume matchen, sondern immer Teilausdrücke, also Teilbäume, die bis zu den Blättern gehen und nicht plötzlich innen aufhören. Das habe ich schon unter dem Namen "bottom-up" gesehen. Probier doch mal, ob Du mit einer Kombination dieser Schlüsselworte weiterkommst; oder mach mal eine präzise Problembeschreibung, das Thema klingt nämlich ganz interessant.

Hallo Jester,

vielen Dank für Deine Antwort. Also die ganze Sache entstammt meinen Babyschritten in der Problematik zur Vereinfachung von mathematischen Thermen. Ich hatte mir einen einfachen "Matcher" geschrieben, der mit Wildcards bestückte Muster über den AST des Mathematischen Ausdrucks schob, und so (Über einen Satz von Regeln "Gematchtes Muster -> Ersetzung") einfache Ersetzungen und Umformungen hinbekam. Erstmal hatte ich mich tierisch gefreut, auf so einfachem Wege so viel zu erreichen. Aber die Ernüchterung kam dann, als ich sah, dass ich so einfach keine Ausklammerung hinbekam, selbst Kürzungen waren nur über dafür handgefertigte Funktionen möglich (immerhin konnte ich diese Funktionen über Regeln selber in den Ausdruck einbauen). Was mich nun seit längeren stört ist, dass ich es nicht hinbekomme, den Matcher so gut zu bauen, dass er dafür keiner weiteren Hilfe bedarf, sondern die Ersetzungsregel " $e1*$ e2 + $e1*$ e3 -> $e1*($ e2+$e3)" angewendet auf "a*b + c*a" genügt um das Ergebnis "a*(b+c)" zu erhalten. (Wobei die $e's für Ausdruck-Wildcards stehen und das ist natürlich der allereinfachste Fall hier! Nur gut, dass ich es nochmal aufgeschrieben habe, weil ich jetzt erkenne, dass der Muster-Term "symmetrisch" sein kann, was wieder die Hälfte aller benötigten Versuche eliminiert).

Leider hatte ich heute nicht genügend Zeit, mich mit Deinen Vorschlägen ausreichend zu beschäftigen. Es tauchte beispielsweise http://basics.sjtu.edu.cn/~liguoqiang/teaching/algo11/materials/AC.pdf in der Suchanfrage auf, was schon ziemlich in meine Richtung zu gehen scheint, aber ich konnte noch nicht erkennen, ob der Algorithmus auch einen präparierten Baum braucht. Außerdem behandelt der Text ja auch Probleme, in der in beiden ASTs "Wildcards" vorkommen, somit habe ich meiner Meinung ein deutlich einfacheres Problem. Bei Springerlink gibt es wohl auch einen Text (http://www.springerlink.com/content/px73735g00958234/), aber das wäre eine 25€ Investition und ich weiß nicht ob am Ende etwas dabei herauskommt...

Viele Grüße,
Deci

Jester

Schick mir mal über das Forum eine Email.