Passen Sie die Permutationen an!

15

Ihre Herausforderung besteht darin, einen regulären Ausdruck zu erstellen, der zu jeder String-Permutation passt, und zu nichts anderem. Bei der Übereinstimmung muss auch zwischen Groß- und Kleinschreibung unterschieden werden.

Also, zum Beispiel, wenn Ihre Regex ist:

ABC

Es sollte mit diesen Zeichenfolgen übereinstimmen (und nur übereinstimmen):

ABC
ACB
BAC
BCA
CAB
CBA

Es sollte nicht mit Dingen wie übereinstimmen:

AABC (contains an extra A)
ABCD (contains an extra D)
AC   (no B)
AAA  (no B and C, extra 2 A's)
abc  (case-sensitive)

Regeln:

  • Sie dürfen jede Regex-Variante verwenden, die Sie mögen.
  • Es gelten Standardlücken.
  • Sie müssen mindestens zwei verschiedene Zeichen in Ihrem Code haben. Das heißt, Lösungen wie 1sind ungültig.
  • Der reguläre Ausdruck sollte nur druckbares ASCII und sonst nichts enthalten.
Clismique
quelle
Ebenfalls verwandt:
Anzahl der
Ich dachte (ABC|ACB|BAC|BCA|CAB|CBA)aber du wolltest eine verallgemeinerte Antwort.
Stephen Quan

Antworten:

11

JavaScript, 64 57 Bytes

4 Bytes entfernt dank Martin Ender.

^(?!.*([^])(.*\1){3}]?)[$$[-^?!!.'''-*11{33}5577\\-]{57}$

Probieren Sie es hier aus.

Erläuterungen (veraltet)

^                                  # Beginning of the string.
(?!.*                              # Match only the strings that don't contain...
  (.)(.*\1){4}                     #     5 occurrences of the same character.
  [^1]?[^1]?                       #     Something that doesn't matter.
)
[]zzz^(?!!!.**[)\\1{{44}}666]{64}  # 64 occurrences of these 16 characters.
                                   # Some are duplicated to make sure the regex
                                   # contains 4 occurrences of each character.
\z                                 # End of the string.
jimmy23013
quelle
2
Ich denke, das funktioniert für 60: ^(?!.*(\S)(.*\1){3}[^1]?)[]zzSS[-^?!!.'''-*1{33}0066-]{60}\z regex101
Martin Ender
Dies funktioniert fast in .NET:^(?'4'(?!(.*\4){3})[]$$[\\^^?!!..'-*{}33-5-]){54}$[5]*
Jimmy23013
Was geht nicht Nachgestellte Zeilenvorschübe?
Martin Ender
@ MartinEnder Ja.
Jimmy23013
2

Perl- und PCRE-Regex, 280 Byte

^(?=(.*z){2})(?=(.*\(){43})(?=(.*\)){43})(?=(.*\*){22})(?=(.*\.){23})(?=(.*0){2})(?=(.*1){6})(?=(.*2){16})(?=(.*3){7})(?=(.*4){4})(?=(.*5){1})(?=(.*6){3})(?=(.*7){2})(?=(.*8){2})(?=(.*9){1})(?=(.*=){22})(?=(.*\?){22})(?=(.*\\){11})(?=(.*\^){2})(?=(.*\{){23})(?=(.*\}){23}).{280}\z

(Etwas) besser lesbar:

^
(?=(.*z){2})
(?=(.*\(){43})
(?=(.*\)){43})
(?=(.*\*){22})
(?=(.*\.){23})
(?=(.*0){2})
(?=(.*1){6})
(?=(.*2){16})
(?=(.*3){7})
(?=(.*4){4})
(?=(.*5){1})
(?=(.*6){3})
(?=(.*7){2})
(?=(.*8){2})
(?=(.*9){1})
(?=(.*=){22})
(?=(.*\?){22})
(?=(.*\\){11})
(?=(.*\^){2})
(?=(.*\{){23})
(?=(.*\}){23})
.{280}\z

Dies läuft in O (2 ^ n) -Zeit ab, wie beschrieben, und ist daher unglaublich ineffizient. Der einfachste Weg, dies zu testen, besteht darin, jedes Vorkommen von .*durch zu ersetzen .*?, wodurch der Fall, in dem es übereinstimmt, zuerst überprüft wird (was bedeutet, dass es in linearer Zeit übereinstimmt, aber immer noch exponentielle Zeit benötigt, wenn es nicht übereinstimmt).

Die Grundidee ist, dass wir die Länge des regulären Ausdrucks auf 280 erzwingen und Lookahead-Aussagen verwenden, um zu erzwingen, dass jedes Zeichen im regulären Ausdruck mindestens eine bestimmte Anzahl von Malen vorkommt, z. B. dass (?=(.*z){2})das zZeichen mindestens zweimal vorkommt. 2+43+43+22+23+2+6+16+7+4+1+3+2+2+1+22+22+11+2+23+23ist 280, wir können also keine "zusätzlichen" Vorkommen von Zeichen haben.

Dies ist ein Programmierbeispiel für ein Autogramm , ein Satz, der sich selbst beschreibt, indem die Nummer jedes darin enthaltenen Zeichens (und in diesem Fall auch die Gesamtlänge) aufgelistet wird. Ich hatte ziemlich viel Glück bei der Erstellung (normalerweise muss man Brute Force anwenden, aber ich bin beim Testen meines Brute-Force-Programms über diese Lösung gestolpert, bevor ich es vollständig fertig geschrieben hatte).

Perl und PCRE regex, 253 Byte, in Zusammenarbeit mit Martin Ender

Ich nahm an, dass es kürzere Lösungen geben könnte, bei denen einige Ziffern weggelassen werden (höchstwahrscheinlich 9, 8 oder 7). Martin Ender hat einen gefunden, siehe unten:

^(?=(.*z){2})(?=(.*\(){39})(?=(.*\)){39})(?=(.*\*){20})(?=(.*\.){21})(?=(.*0){4})(?=(.*1){6})(?=(.*2){11})(?=(.*3){6})(?=(.*4){3})(?=(.*5){2})(?=(.*6){3})(?=(.*9){4})(?=(.*=){20})(?=(.*\?){20})(?=(.*\\){9})(?=(.*\^){2})(?=(.*{){21})(?=(.*}){21}).{253}\z

Lesbare Version:

^
(? = (. * z) {2})
(? = (. * \ () {39})
(? = (. * \)) {39})
(? = (. * \ *) {20})
(? = (. * \.) {21})
(? = (. * 0) {4})
(? = (. * 1) {6})
(? = (. * 2) {11})
(? = (. * 3) {6})
(? = (. * 4) {3})
(? = (. * 5) {2})
(? = (. * 6) {3})
(? = (. * 9) {4})
(? = (. * =) {20})
(? = (. * \?) {20})
(? = (. * \\) {9})
(? = (. * \ ^) {2})
(? = (. * {) {21})
(? = (. *}) {21})
. {253} \ z

quelle
Ich glaube nicht, dass Sie denen {}in den letzten beiden Lookaheads entkommen müssen . Sie müssen auch keine Dinge wie hinzufügen, (?=(.*5){1})da es keine gäbe, 5wenn Sie nicht diesen Lookahead hätten. Ein Problem ist, $dass ein nachlaufender Zeilenvorschub möglich ist, sodass Sie diesen \zanstelle von $jimmy verwenden müssen, aber das kostet Sie, glaube ich, kein Byte, da Sie den \im ersten Lookahead speichern .
Martin Ender
Mir ist bewusst, dass es möglich ist, Dinge wie Ziffern wegzulassen. Sie sind jedoch dazu da, das Autogramm zum Laufen zu bringen . Wenn Sie einen Teil des Programms entfernen, wird der gesamte Rest unterbrochen, da das Programm nicht mehr korrekt beschrieben wird. (Die Zählungen für jede Zeile zählen die Zählungen für jede Zeile! Daher ist es im Allgemeinen unmöglich, das Programm zu ändern.) Das $Zulassen einer neuen Zeile am Ende der Zeichenfolge hängt im Allgemeinen davon ab, wie der reguläre Ausdruck von der Umgebung aufgerufen wird Programm (normalerweise werden sie mit Code ausgeführt, der bereits in Zeilen zerlegt wurde).
Genauer gesagt: Ich brauche das (?=(.*5){1})in diesem Fall. Wenn ich es entfernen würde, gäbe es eine 5 im Programm, weil die (?=(.*1){6})Zeile jetzt lesen müsste (?=(.*1){5}).
Was den abschließenden Zeilenvorschub angeht, so scheint es keine Einschränkung in der Herausforderung bezüglich der Art der Eingabe in Ihre Regex zu geben. Das bedeutet normalerweise, dass es für jede beliebige Zeichenfolge funktionieren sollte und der Wechsel $zu " \znicht schaden" (und "nicht schaden") das Autogramm nicht brechen).
Martin Ender
Oh, ich verstehe; Sie ändern die \$$zu z\z. Das funktioniert; Ich werde es ändern gehen.