Pandigital Regex?

Question

Wie lautet ein regulärer Ausdruck, der prüft, ob eine Zeichenkette pandigital ist (alle Ziffern von 1 bis 9 genau einmal enthält)?

Zum Beispiel:

123456789
891364572

Aber nein:

11234556789
25896471

Ich weiß, wie man das ohne Regex macht, aber ich war nicht in der Lage, eine Regex dafür zu bilden.

Danke.

Dies ist keine Hausaufgabe.

Answer 1

Kurz und bündig, mit einer negativen Vorausschau:

/^(?!.*([1-9]).*\1)[1-9]{9}$/

• [1-9] ist die Zeichenklasse für Ziffern ungleich Null - gleichbedeutend mit [123456789]
• .* passt auf jede Zeichenkette beliebiger Länge.
• .*([1-9]).*\1.* passt auf jede Zeichenkette, die mindestens zwei Mal dieselbe Ziffer, die nicht Null ist, enthält
  • eine Nicht-Null-Stelle wird abgeglichen und erfasst durch ([1-9])
  • eine Wiederholung dieser Ziffer, die nicht Null ist, wird erfüllt durch \1 , a Rückverweis zum ersten gefangenen Spiel.
  • die .* stimmt mit der willkürlichen Auffüllung vor und zwischen der Nicht-Null-Ziffer und ihrer Wiederholung überein.
• (?!_<pattern>_) passt auf jede Stelle, an der das enthaltene Muster nicht Spiel. Dies ist eine negative Vorausschau da es nur mit einer Position in der Zeichenkette und konsumiert nichts davon - er schaut nur voraus, um sie mit dem enthaltenen Muster zu vergleichen.
• [1-9]{9} stimmt mit neun nicht-zeo Ziffern überein.
  • _<pattern>_{9} bedeutet, dass das vorangehende Muster 9 Mal übereinstimmt.
• ^_<pattern>_$ stimmt mit jeder Zeichenkette überein, die genau mit dem enthaltenen Muster übereinstimmt (und nicht eine Teilzeichenkette enthält, die mit dem Muster übereinstimmt)
  • ^ passt auf die Position am Anfang einer Zeichenkette ODER den Anfang einer Zeile
  • $ entspricht der Position am Ende einer Zeichenkette ODER dem Ende einer Zeile

Wir prüfen also zunächst, ob sich keine Ziffern wiederholen, und dann, ob es sich nur um Ziffern handelt. Da sie 9 Ziffern lang ist und sich keine wiederholt, müssen alle genau einmal vorkommen. Das ist die Schubladenprinzip bei der Arbeit!

Die Syntax für Ihre spezielle Engine für reguläre Ausdrücke kann variieren. Der obige Ausdruck ist ein PCRE (unterstützt in Perl, Ruby und einer Reihe anderer Sprachen). Posix reguläre Ausdrücke haben eine leicht unterschiedliche Syntax. Nicht alle Engines unterstützen negative Lookaheads, aber die meisten unterstützen Back-References. Beide sind nicht Teil der Definition formaler theoretischer regulärer Ausdrücke, sind aber sehr praktisch.

Answer 2

Regex ist nicht gerade das beste Werkzeug für diese Aufgabe, aber hier ist es:

^(?=[^1]*1[^1]*$)(?=[^2]*2[^2]*$)(?=[^3]*3[^3]*$)(?=[^4]*4[^4]*$)(?=[^5]*5[^5]*$)(?=[^6]*6[^6]*$)(?=[^7]*7[^7]*$)(?=[^8]*8[^8]*$)(?=[^9]*9[^9]*$)[1-9]+$

(?= ) ist eine Vorausschau. Er passt nicht wirklich zur Beschreibung regulärer Ausdrücke, da er keine reguläre Sprache beschreibt.

Answer 3

Wenn es keine Hausaufgaben sind, sollten Sie keine REs verwenden. Der folgende C-Code sollte ein guter Anfang sein.

#include <stdio.h>
int isPandigital (char *inputStr) {
    /* Initial used states of false. */
    char used[] = {0,0,0,0,0,0,0,0,0,0};

    int count = 0;
    char ch;

    /* Process each character in string. */

    while ((ch = *inputStr++) != '\0') {
        /* Non-numeric, bad. */
        if ((ch < '0') || (ch > '9')) {
            return 0;
        }

        /* Too many, bad. */
        if (++count > 9) {
            return 0;
        }

        /* Multiples, bad. */
        if (used[ch - '0']) {
            return 0;
        }

        /* Store fact that this one's been used. */
        used[ch - '0'] = 1;
    }

    /* Good or bad depending on how many we've had. */
    return (count == 9);
}

int main (int argCount, char *argVar[]) {
    int i;
    for (i = 1; i < argCount; i++) {
        if (isPandigital (argVar[i])) {
            printf ("'%s' is pandigital\n", argVar[i]);
        } else {
            printf ("'%s' is NOT pandigital\n", argVar[i]);
        }
    }
    return 0;
}

Verwendung Ihrer Testdaten:

$ pandigital 123456789 891364572 11234556789 25896471

erhalten wir die folgenden Ergebnisse:

'123456789' is pandigital
'891364572' is pandigital
'11234556789' is NOT pandigital
'25896471' is NOT pandigital

Answer 4

Es wäre viel einfacher, dies in prozeduralem Code zu tun, indem man jedes Zeichen in einer Schleife durchläuft und sie in einem Array markiert, ... oder ist das eine Hausaufgabe?

Answer 5

bool chk(string s, int idx, set sofar) {
  return index == s.length ? true : isdigit(s[idx]) && !sofar.count(s[idx]) && chk(s,++idx,sofar.insert(s[idx]));
}

So etwas könnte funktionieren. Ich habe mir nicht die Mühe gemacht, es zu überprüfen.