Pchełki Python, odcinek 3: kombinujemy

https://xpil.eu/rY5PU

Jeżeli ktoś zagląda na tego bloga częściej niż raz w życiu...

Takich osób jest zaskakująco dużo (ale nigdy więcej niż jedna na raz), na przykład ktoś szukający tekstu "paraboliczny kondensator moczu wielbłąda dżungarskiego" znajdzie go właśnie tutaj; szanse, że to ten sam człowiek szukać będzie informacji o trzpieniu wału korbowego lewoskrętnej przekładni Torquiste'a są praktycznie równe zeru.

... częściej niż raz w życiu, powiadam, może niejasno kojarzyć moje niegdysiejsze próby anagramowania za pomocą SQL-a. Na przykład w tym oto wpisie podejmowałem próby wyszukiwania siedmioliterowych słówek z zestawu piętnastu liter.

Dziś poanagramujemy sobie w Pythonie. Zadanie brzmi: z zestawu piętnastu liter znaleźć wszystkie słowa nie krótsze niż pewna zadana dolna wartość (na przykład siedem).

Najpierw kod:

import itertools
min_len, letters_in, words_filename = (7, "apanelecnonglhye", r'c:\Users\admin\Downloads\wordlist\2of4brif.txt')
cmb=[]
for i in range(min_len,len(letters_in)):
    for c in itertools.combinations(list(letters_in), i):
        cmb.append(''.join(sorted(''.join(c))))
f = open(words_filename)
words = f.read().split(sep="\n")
f.close()
wordsl = words[:]
for i, wrd in enumerate(wordsl): wordsl[i] = ''.join(sorted(wrd))
i_sect = set(cmb).intersection(wordsl)
results = []
for i, comb in enumerate(i_sect): results.append(words[wordsl.index(comb)])
results.sort(key=len, reverse=True)
print(results)

A po kodzie, jak to mam we zwyczaju, szybki opis.

Tym razem zamiast kopiować kod, będę się odwoływał do numerów linii:

1: Biblioteka itertools udostępnia całe naręcze narzędzi do generowania permutacji, kombinacji i innych -acji

2: Tu definiujemy dane wejściowe, czyli minimalną długość poszukiwanego słowa, listę liter, z których będziemy próbować układać słowa, oraz ścieżkę do pliku ze słownikiem

3: Inicjalizujemy listę cmb (a więc, mówimy Pythonowi, że cmb jest listą pustą)

4, 5, 6: Tu dzieje się całkiem sporo. W zewnętrznej pętli iterujemy po długościach wyszukiwanych słów, począwszy od długości minimalnej (tu: 7) aż do długości maksymalnej, czyli do ilości liter na wejściu (zmienna letters_in). W wewnętrznej pętli zaś iterujemy po wszystkich kombinacjach i-literowych zadanych liter. Słówko 'list' pojawia się tam, ponieważ funkcja combinations oczekuje na wejściu listy a nie tekstu.  Wreszcie w szóstej linii dodajemy znalezioną kombinację do listy cmb. Najbardziej wewnętrzne ''.join(c)' składa kombinację c (listę) z powrotem do tekstu, następnie funkcja sorted sortuje znaki w tym tekście alfabetycznie, zwracając listę, którą (ponownie) składamy do tekstu zewnętrzną funkcją join.

7: Otwieramy plik tekstowy ze słownikiem. Oczekiwany format pliku to jedno słowo w każdej linii; linie rozdzielone znakami końca linii ("\n").

8: Wczytujemy zawartość słownika do zmiennej words, dzieląc słownik na pojedyncze wyrazy.

9: Zamykamy plik słownika

10: Zmienną wordsl tworzymy jako kopię zmiennej words. Dwukropek w nawiasie kwadratowym spowoduje, że wordsl będzie faktycznie kopią całej listy words a nie tylko kopią referencji do tej samej listy.

11: W każdym ze słów z listy wordsl sortujemy litery. Na przykład słowo 'and' zostanie zamienione na 'adn', a słowo 'hush' na 'hhsu'

12: Znajdujemy część wpólną zbioru wszystkich kombinacji liter wejściowych ze zbiorem wszystkich zestawów liter ze słownika. Znalezioną część wpólną zapisujemy do zmiennej i_sect (InterSection czyli przecięcie)

13: Inicjalizujemy zmienną results na listę pustą

14: Tutaj dołączamy do wyników (lista results) słowa z listy words, które składają się z pasujących zestawów liter. Tego typu wyrażenia trzeba rozkładać od środka, a więc: comb to kombinacja w bieżącej iteracji. index(comb) to pozycja tej kombinacji w liście wordsl. Ten indeks pozwala na wyszukanie oryginalnego słowa w liście words (słowo to znajduje się na tej samej pozycji, ponieważ od chwili skopiowania listy w linii 10 nie zmienialiśmy kolejności elementów listy).

15: Sortujemy listę wyników, malejąco według długości elementów. Przydaje się tutaj opcjonalny parametr key, któremu można przekazać nazwę funkcji, która zostanie wykonana na każdym z sortowanych elementów. W tym przypadku funkcją jest len, czyli wyznaczenie długości tekstu. Bardzo wygodne.

16: Wypisujemy wyniki.

Przypuszczam, że powyższe rozwiązanie jest dalekie od optymalnego - jednak dla słownika z 60,000 angielskich słówek działa całkiem sprawnie (poniżej 1s). W przypadku słownika polskiego (2.7 mln słówek) działa ciut wolniej, ale nadal do wytrzymania (poniżej 4s).

https://xpil.eu/rY5PU