Generieren Sie Zeichenfolgen, die immer einen bestimmten Buchstaben python enthalten

Question

Ich möchte Wörter und einen Buchstaben generieren. Aber alle generierten Wörter müssen diesen Buchstaben enthalten. Ich erzeuge eine sehr große Menge an Wörtern. So ist es sehr ineffizient zu sagen:

(word for word in self.getWords(letters, 8) if letter in word) 

oder etwas Äquivalentes.

getWords Code:

def getWords(self, iterable, maxDepth): 
    allWords = [] 
    for depth in range(3, maxDepth + 1): 
     for word in itertools.permutations(iterable, depth): 
      allWords.append("".join(word)) 

Ich möchte getWords haben nur über Worte mit letter in ihnen denken. Gibt es eine Möglichkeit itertools zu verwenden, um dieses Ergebnis zu erreichen?

Answer 1

Zuerst die Teilmenge von Wörtern erzeugen, die den Buchstaben enthalten, die Sie wollen:

def subset(char, words): 
    return set([word for word in words if char in word.lower()]) 

bsub = subset("b", words) 

Dann können Sie eine zufällige Stichprobe von diesen Worten nehmen:

# Take 100 random words which contain the letter b. 
result = random.sample(bsub, 100) 

Alternativ kann durch Modifizieren getWords können wir Wörter filtern, die nicht den erforderlichen Buchstaben enthalten:

Es ist auch wert Erwähnen: wenn jedes Wort in allWords einzigartig ist, wird die Umwandlung in eine set() den Mitgliedschaftstest von O(n) auf O(1) reduzieren.

Sets sind schneller, weil sie nicht die gesamte Liste durchlaufen müssen, um die Mitgliedschaft zu testen. Strings sind unveränderlich, also sind sie Hashes, was bedeutet, dass Mitgliedschaftstests konstante Zeit benötigen.

In Ihrem Fall führen Sie keine Mitgliedschaft durch, daher führt die Konvertierung in Mengen nicht zu einer merklichen Steigerung der Geschwindigkeit, aber die Auswahl einer Untermenge beschleunigt die Prüfung, da dann jede Generation nicht getestet werden muss für die Gültigkeit.