☰

So finden Sie Wörter, die einer bestimmten Reihenfolge folgen

tag-icon • tag-icon bash shell-script scripting
So finden Sie Wörter, die einer bestimmten Reihenfolge folgen

Ich versuche, ein Skript (script1.sh) zu schreiben, das bei einem Buchstabensalat alle möglichen Wörter findet.

  • Die Wörter müssen mit dem ersten Buchstaben des Buchstabensalats beginnen und mit dem letzten Buchstaben enden.

  • Die Buchstaben des Wortes müssen der Reihenfolge der Buchstaben im Buchstabensalat entsprechen.

  • Jeder Buchstabe im Buchstabensalat kann mehr als einmal vorkommen.

Also das

./script1.sh "qwertyuytresdftyuiokn"

sollte „und“ ausgeben queen, questionaber nicht „quieten“, da im Buchstabensalat „e“ vor „u“ und „i“ steht.

Ich habe versucht, den ersten, letzten und restlichen Buchstaben Variablen zuzuweisen und dann egrep zu verwenden, um die Wörter zu finden, aber ich konnte keine Möglichkeit finden, die Reihenfolge der Buchstaben zu verwenden. Daher erhalte ich auch hier ungültige Wörter.

#!/bin/bash

first_letter=$(echo $@ | cut -c1)
last_letter=$(echo $@ |rev| cut -c1)
remaining_letters=$(echo $@ | cut -c2- | rev | cut -c2-)

grep -E "^$first_letter[$remaining_letters]*$last_letter$" /usr/share/dict/words

Dann habe ich versucht, aus dem Durcheinander eine Anordnung zu machen, konnte aber auch hier keine Möglichkeit finden, Wörter zu finden, die der Reihenfolge im Durcheinander entsprechen.

Antwort1

#!/bin/sh
pttrn="^$(printf '%s' "$1" | sed -e 's/\(.\)/\1*/g' -e 's/\*/\\+/' -e 's/\*$/\\+/')"'$'
grep "$pttrn" /usr/share/dict/words

Aus dem ersten Argument wird ein Muster gewonnen, indem *nach jedem Zeichen ein eingefügt wird. Dann wird das erste *in geändert \+; ebenso das letzte *. Zusätzlich werden ^und $hinzugefügt. Ihre Beispieleingabe erzeugt das folgende Muster:

^q\+w*e*r*t*y*u*y*t*r*e*s*d*f*t*y*u*i*o*k*n\+$

Dieses Muster ist das richtige Muster für grep. qmuss mindestens einmal am Anfang vorkommen, nmuss mindestens einmal am Ende vorkommen. Jeder Buchstabe in der Mitte darf null oder mehrmals vorkommen, die Reihenfolge bleibt erhalten.

Beachten Sie, dass das Skript dumm ist. Wenn Sie die Eingabe mit ., [, ]oder so vornehmen, erhalten Sie einen regulären Ausdruck, der über die Spezifikation hinausgeht. Geben Sie eine sinnvolle Eingabe ein oder erweitern Sie das Skript, um es zu validieren.

Beispiele:

$ ./script1.sh qwertyuytresdftyuiokn
queen
question
$ ./script1.sh te
tee
$ ./script1.sh superuser
seer
serer
spur
super
supper
surer
$

Antwort2

Hier ist eine Möglichkeit, es anzugehen

Filtern Sie zunächst die Wortliste auf die Wörter, die mit den gleichen Buchstaben beginnen und enden wie das Durcheinander. Wenn beispielsweise das Durcheinander als Positionsparameter übergeben wird $1(und eine aktuelle bashShell angenommen wird),

grep -x "${1:0:1}.*${1:(-1):1}" /usr/share/dict/words

Dann nehmen Sie jedes dieser Wörter und zerlegen es in einen regulären Ausdruck - mir fällt keine "schöne" Möglichkeit ein, das zu tun, aber mit GNU sed könnten Sie zum Beispiel

$ sed -E 's/(.)\1*/+.*\1/2g' <<< "queen"
q+.*u+.*e+.*n

Testen Sie nun das Durcheinander mit jedem generierten Muster.

Alles zusammen:

$ cat script1 
#!/bin/bash

wordlist=/usr/share/dict/words

while IFS= read -r word; do 
  grep -qEx "$(sed -E 's/(.)\1*/+.*\1/2g' <<< "$word")" <<< "$1" && printf '%s\n' "$word"
done < <(grep -x "${1:0:1}.*${1:(-1):1}" "$wordlist")

Dann

$ ./script1 qwertyuytresdftyuiokn
queen
question

Antwort3

Hier ist ein weiteres (ausgeführt in bash). Der pythonCode generiert den regulären Ausdruck und gibt ihn an weiter grep. grepAnschließend wird die Ausgabe des bewährten lookDienstprogramms bearbeitet, das eine binäre Suche durchführt, um alle Wörter zurückzuholen, die im Beispiel /usr/share/dict/wordsmit beginnen . Somit ist die zu durchsuchende Menge an Wörtern stark reduziert.qgrep

python3 -c 'import sys
arr = list(sys.argv[1])
print(*arr, sep="*")
' $1 | grep -x -f - <(look ${1:0:1})

Alternativ eine look+ python3Lösung, die reguläre Ausdrücke vermeidet

look q | ./finder.py "qwertyuytresdftyuiokn"

wobei finder.pygilt:

#!/usr/bin/env python3
import sys
from itertools import groupby

seek_word = sys.argv[1]
for word in sys.stdin:
    orig_word = word.strip()
    word = ''.join(k for k, g in groupby(orig_word)) 
    s_w = iter(seek_word)
    i_word = iter(word)
    if all(c in s_w for c in i_word) and not next(s_w, None):
        print(orig_word)

verwandte Informationen