Ver-undung in Regulären Ausdrücken

Hallo,

gibt es die Möglichkeit bei der Suche mit Regulären Ausdrücken eine Verundung
der Suchterme zu verwenden?
D.h. ich durchsuche alle Zeilen eines Dokuments und will mir die ausgeben
lassen, die die Wörter x1, x2 und x3 enthalten. Allerdings unabhängig von der auftrenden Reihenfolge.
Bei "x1?.*x2?.*x3?" spielt ja die Reihenfolge eine Rolle, "x1?|x2?|x3?" berücksichtigt nicht alle x_n Terme.

Christoph

Wenn du nichts weiteres über die strings weißt, geht das meines Wissens nach nicht, ohne alle Permutationen aufzuschreiben. Also
(x1?.*x2?.*x3)|(x2?.*x1?.*x3)|(x2?.*x3?.*x1)|...

Das ist so ähnlich wie bei der konjunktiven Normalform für aussagenlogische Formeln, denke ich: Man kann das Gewünschte zwar ausdrücken, aber der Ausdruck wird sehr lang. "Alle von n verschiedenen String suchen ohne Beachtung der Reihenfolge" wird AFAIK einen regulären Ausdruck ergeben, dessen Länge exponentiell in n ist.

Das zu beweisen könnte so gehen: Es könnte schon reichen festzustellen, dass jeder endliche deterministische Automat, der deine Sprache erkennt, exponentiell viele Zustände besitzen muss. Das muss er, weil der Automat sich ja merken muss, welche Strings schon aufgetreten sind. Es gibt aber exponentiell viele mögliche Kombinationen von "strings die schon aufgetreten sind", daher braucht er exponentiell viele Zustände.

Ob eine exponentielle untere Schranke für die Anzahl der Zustände eines endlichen deterministischen Automaten zwangsläufig auch zu exponentiell langen dazugehörigen regex führt, das weiß ich nicht. Ich würde schätzen, dass das so sein muss, aber einen Beweis dafür hab ich grad nicht gefunden.

Christoph schrieb:

Wenn du nichts weiteres über die strings weißt, geht das meines Wissens nach nicht, ohne alle Permutationen aufzuschreiben. Also
(x1?.*x2?.*x3)|(x2?.*x1?.*x3)|(x2?.*x3?.*x1)|...
...

Schaaaaade ... Hab ich mir aber schon gedacht. Die Anzahl der möglichen Verknüpfungen beträgt dabei allerding n-Fakultät - also bei 10 Suchtermen ne ganze Menge.
Ich hoffe die .NET Regex-Engine unterstützt das überhaupt.

Bashar

Prüfe doch einfach jede Zeile darauf, ob sie die 10 regulären Ausdrücke enthält. Ich weiß, dass das nicht 100%ig äquivalent ist zu dem, was du fragst, aber trotzdem.