Ausmultiplizieren von Listen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Clython
User
Beiträge: 151
Registriert: Samstag 21. August 2004, 13:58
Wohnort: Schweiz, BE-2500

Ausmultiplizieren von Listen

Beitragvon Clython » Freitag 8. Dezember 2006, 14:34

Hallo,

ich bin gerade daran einen Parser für meine Python-Reimplementation von TIGERSearch zu schreiben. Dazu muss ich boolsche Anfragen parsen und normalisieren. Dazu muss ich Listen "ausmultiplizieren". Z.B;

A & B | C

Ergibt: [[A, B], [A,C]]

oder

( A | B | C ) & D & ( E | F )

Ergibt:

[
[A, D, E],
[A, D, F],
[B, D, E],
[B, D, F],
[C. D. E],
[C, D, F]]

Kann mir jemand einen Tipp geben (keinen Code!), wie ich das Problem am besten angehe? Gibt es da möglicherweise etwas in den Batterien, das ich übersehen habe? Meine bisherigen Implementationen lassen etwas zu wünschen übrig, und ich habe mich gefragt, ob es möglicherweise eine bessere Methode gibt.

Vielen Dank für die Tipps
BlackJack

Re: Ausmultiplizieren von Listen

Beitragvon BlackJack » Freitag 8. Dezember 2006, 15:26

Clython hat geschrieben:A & B | C

Ergibt: [[A, B], [A,C]]


Hm, insbesondere wenn ich Dein zweites Beispiel anschaue, dann hätte ich eher [[A, B], [C]] erwartet. `&` bindet stärker als `|`. Aber Du hast sicher nur die Klammern vergessen. :-)

oder

( A | B | C ) & D & ( E | F )

Ergibt:

[
[A, D, E],
[A, D, F],
[B, D, E],
[B, D, F],
[C. D. E],
[C, D, F]]

Kann mir jemand einen Tipp geben (keinen Code!), wie ich das Problem am besten angehe? Gibt es da möglicherweise etwas in den Batterien, das ich übersehen habe? Meine bisherigen Implementationen lassen etwas zu wünschen übrig, und ich habe mich gefragt, ob es möglicherweise eine bessere Methode gibt.


Ohne zu wissen was Du implementiert hast, lässt sich schlecht sagen ob ein Vorschlag besser ist. ;-)

Hast Du die Ausdrücke immer in dieser Form? Also so das man sie als Liste darstellen kann in der die "oder"-Elemente ihrerseits in Listen zusammengefasst sind? Dein zweites Beispiel wäre also als Eingabe für eine Funktion [[A, B, C], [D], [E, F]].

Dann gibt's zwei Wege. Eine einfache rekursive Lösung, oder Du bastelst Dir eine Art "Zählwerk". Dazu brauchst Du einen Zähler/Index pro Unterliste die alle bei 0 anfangen. Wenn der erste noch kleiner ist als die Länge seiner Liste, dann zählst Du ihn einen rauf. Ansonsten setzt Du ihn wieder auf 0 und zählst den nächsthöheren Zähler/Index nach dem gleichen Muster hoch. Für das zweite Beispiel ergeben sich also die folgenden Zählerstände:

[0, 0, 0]
[1, 0, 0]
[2, 0, 0]
[0, 0, 1]
[1, 0, 1]
[2, 0, 1]

Wenn man den letzten Zähler auch nochmal um eins raufzählen wollte, dann würde es einen "Übertrag" geben. Das ist das Zeichen aufzuhören.

Willst Du alle Möglichkeiten aufzählen um die dann gegen etwas zu testen? Das ginge bei "und"- und "oder"-Verknüpfungen sicher effizienter wenn Du die Stück für Stück auswertest, anstatt alle Kombinationen aufzuzählen. Vor allem weil man vorzeitig aufhören kann, wenn das Ergebnis sich nicht mehr ändern kann.
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Beitragvon keppla » Freitag 8. Dezember 2006, 15:31

Ich würde vermutlich so herangehen, dass ich erstmal den zu multiplizierenden Ausdruck korrekt in eine Struktur bekomme, also, dass

a & b | c

in etwa durch irgendwelche Baumartigen Objekte repräsentiert wird, bei denen (wenn ich deine Präzedenzen richtig verstanden habe) das oberste objekt ein "und" ist, welches als kinder das atom a, und ein "oder" mit den kindern b und c hat.
Dann könnte man den Objekten beibringen, dass sie ihre Wahrheitslisten, indem sie die ihrer kinder verschmelzen.
Clython
User
Beiträge: 151
Registriert: Samstag 21. August 2004, 13:58
Wohnort: Schweiz, BE-2500

Re: Ausmultiplizieren von Listen

Beitragvon Clython » Freitag 8. Dezember 2006, 15:37

BlackJack hat geschrieben:
Clython hat geschrieben:A & B | C

Ergibt: [[A, B], [A,C]]


Hm, insbesondere wenn ich Dein zweites Beispiel anschaue, dann hätte ich eher [[A, B], [C]] erwartet. `&` bindet stärker als `|`. Aber Du hast sicher nur die Klammern vergessen. :-)


Nein, ich habe die Klammer nicht vergessen, ich hätte es nur so schreiben sollen:
[[A & D & E] | [A & D & F] | ...]

Hilft das jetzt weiter? Gibt es vielleicht irgendwo eine implementation eines boolschen Parsers?
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Re: Ausmultiplizieren von Listen

Beitragvon keppla » Freitag 8. Dezember 2006, 15:45

Clython hat geschrieben:Hilft das jetzt weiter? Gibt es vielleicht irgendwo eine implementation eines boolschen Parsers?


Ja gibt es: python kann boolsche ausdrücke auswerten, wenn du | durch or und & durch and ersetzt :twisted:
ne, ernsthaft, solange du nur buchstaben, klammern und &/| hast, ist so ein Parser nicht all zu schwer zu basteln. Es gibt auch Bibliotheken, die einem den Parserbau vereinfachen (PyParse oder so).
BlackJack

Re: Ausmultiplizieren von Listen

Beitragvon BlackJack » Freitag 8. Dezember 2006, 15:57

Clython hat geschrieben:
BlackJack hat geschrieben:
Clython hat geschrieben:A & B | C

Ergibt: [[A, B], [A,C]]


Hm, insbesondere wenn ich Dein zweites Beispiel anschaue, dann hätte ich eher [[A, B], [C]] erwartet. `&` bindet stärker als `|`. Aber Du hast sicher nur die Klammern vergessen. :-)


Nein, ich habe die Klammer nicht vergessen, ich hätte es nur so schreiben sollen:
[[A & D & E] | [A & D & F] | ...]


Ich meinte bei ``A & B | C`` hast Du die Klammern vergessen. Das müsste `` A & (B | C)`` heissen um zu Deinem Ergebnis zu passen.

Zum Parsen: Ich habe mit `PyParsing` ganz gute Erfahrungen gemacht.
burnt99
User
Beiträge: 1
Registriert: Donnerstag 9. August 2007, 15:07

Gleiches Problem

Beitragvon burnt99 » Donnerstag 9. August 2007, 15:14

Hallo,

ich habe zur Zeit das gleiche Problem zu loesen. Allerdings moechte ich das ganze in Ruby implementieren. Daher bin ich eher allgemein an der Beschreibung eines Algorithmus interessiert. Ich weiss, dass das hier nicht das richtige Forum ist, aber dieser Thread war die einzige Quelle im Netz, die ich dazu gefunden habe. Kann mir vielleicht jemand weiterhelfen? Auch Links wuerden weiterhelfen.

Vielen Dank!
BlackJack

Beitragvon BlackJack » Donnerstag 9. August 2007, 15:44

Es wurde ja schon einiges hier gesagt. Kannst Du das Problem dass Du hast etwas präzisieren? Wie sieht die Eingabe aus? Hängts am Parsen oder am "ausmultiplizieren"?

Wer ist online?

Mitglieder in diesem Forum: __deets__, Bing [Bot], Majestic-12 [Bot], Yahoo [Bot], !false