Ausmultiplizieren von Listen

[Clython]

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]

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.

[keppla]

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]

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?

[keppla]

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
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]

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]

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]

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"?