Jak wiele wspólnych angielskich słów z 4 liter lub więcej można zrobić z liter danego słowa (każda litera może być użyta tylko raz)

Question

Na odwrocie kalendarza grupowego znalazłem następującą zagadkę:

Ile często angielskich słów z 4 lub więcej liter można zrobić z liter słowa "podręcznik" (każda litera może być użyta tylko raz).

Moje pierwsze rozwiązanie, które wymyśliłem było:

from itertools import permutations 

with open('/usr/share/dict/words') as f: 
    words = f.readlines() 

words = map(lambda x: x.strip(), words) 

given_word = 'textbook' 

found_words = [] 

ps = (permutations(given_word, i) for i in range(4, len(given_word)+1)) 

for p in ps: 
    for word in map(''.join, p): 
     if word in words and word != given_word: 
      found_words.append(word) 
print set(found_words) 

To daje wynik set(['tote', 'oboe', 'text', 'boot', 'took', 'toot', 'book', 'toke', 'betook']) ale trwało ponad 7 minut na moim komputerze.

Moja następna iteracja brzmiała:

with open('/usr/share/dict/words') as f: 
    words = f.readlines() 

words = map(lambda x: x.strip(), words) 

given_word = 'textbook' 

print [word for word in words if len(word) >= 4 and sorted(filter(lambda letter: letter in word, given_word)) == sorted(word) and word != given_word] 

które zwracają odpowiedź niemal natychmiast, ale dał za odpowiedź: ['book', 'oboe', 'text', 'toot']

Jaki jest najszybszy i najbardziej pythonic poprawne rozwiązanie tego problemu?

(edycja: dodano moje wcześniejsze rozwiązanie permutacji i jego różne wyniki).

Answer 1

Pomyślałem, że podzielę się tą nieco interesującą sztuczką, choć zajmuje ona znacznie więcej kodu niż reszta i nie jest tak naprawdę "pytoniczna". To zajmie znacznie więcej kodu niż inne rozwiązania, ale powinno być raczej szybkie, jeśli spojrzę na czas potrzebny innym.

Wykonujemy trochę wstępnego przetwarzania, aby przyspieszyć obliczenia. Podstawowe podejście jest następujące: Każdej literze w alfabecie przypisujemy pierwszą liczbę. Na przykład. A = 2, B = 3 i tak dalej. Następnie obliczamy hash dla każdego słowa w alfabecie, które jest po prostu produktem głównych reprezentacji każdego znaku w słowie. Następnie przechowujemy każde słowo w słowniku indeksowanym przez skrót.

Teraz, jeśli chcemy dowiedzieć się, które słowa są równoważne powiedzeniu textbook, musimy tylko obliczyć ten sam skrót dla słowa i wyszukać go w naszym słowniku.Zwykle (powiedzmy w C++) musielibyśmy się martwić przepełnieniami, ale w pythonie jest jeszcze prostsze: każde słowo na liście o tym samym indeksie będzie zawierało dokładnie te same znaki.

Oto kod z niewielką optymalizacją, że w naszym przypadku musimy się tylko martwić o znaki pojawiające się również w danym słowie, co oznacza, że ​​możemy uzyskać o wiele mniejszy stół główny niż w innych przypadkach (oczywistą optymalizacją byłoby tylko przypisywać znaki, które pojawiają się w słowie wartością - w każdym razie było wystarczająco szybko, więc nie zawracałem sobie głowy iw ten sposób mogliśmy wstępnie przetworzyć tylko jeden raz i zrobić to dla kilku słów). Algorytm prime jest przydatna dość często więc trzeba mieć samemu zresztą;)

from collections import defaultdict 
from itertools import permutations 

PRIMES = list(gen_primes(256)) # some arbitrary prime generator 

def get_dict(path): 
    res = defaultdict(list) 
    with open(path, "r") as file: 
     for line in file.readlines(): 
      word = line.strip().upper() 
      hash = compute_hash(word) 
      res[hash].append(word) 
    return res 

def compute_hash(word): 
    hash = 1 
    for char in word: 
     try: 
      hash *= PRIMES[ord(char) - ord(' ')] 
     except IndexError: 
      # contains some character out of range - always 0 for our purposes 
      return 0 
    return hash 

def get_result(path, given_word): 
    words = get_dict(path) 
    given_word = given_word.upper() 
    result = set() 
    powerset = lambda x: powerset(x[1:]) + [x[:1] + y for y in powerset(x[1:])] if x else [x] 
    for word in (word for word in powerset(given_word) if len(word) >= 4): 
     hash = compute_hash(word) 
     for equiv in words[hash]: 
      result.add(equiv) 
    return result 

if __name__ == '__main__': 
    path = "dict.txt" 
    given_word = "textbook" 
    result = get_result(path, given_word) 
    print(result) 

Działa na mojej liście ubuntu słowo (98k słowa) dość szybko, ale nie nazwałbym pythonic ponieważ w zasadzie port algorytm C++. Przydatne, jeśli chcesz porównać więcej niż jedno słowo w ten sposób ..

Answer 2

Istnieje generator itertools.permutations, za pomocą którego można zebrać wszystkie permutacje sekwencji o określonej długości. To ułatwia:

from itertools import permutations 

GIVEN_WORD = 'textbook' 

with open('/usr/share/dict/words', 'r') as f: 
    words = [s.strip() for s in f.readlines()] 

print len(filter(lambda x: ''.join(x) in words, permutations(GIVEN_WORD, 4))) 

Edytuj nr 1: Oh! Jest napisane "4 lub więcej";) Zapomnij o tym, co powiedziałem!

Edit # 2: Jest to druga wersja wymyśliłem:

LETTERS = set('textbook') 

with open('/usr/share/dict/words') as f: 
    WORDS = filter(lambda x: len(x) >= 4, [l.strip() for l in f]) 

matching = filter(lambda x: set(x).issubset(LETTERS) and all([x.count(c) == 1 for c in x]), WORDS) 
print len(matching) 

Answer 3

Jak ten temat?

from itertools import permutations, chain 

with open('/usr/share/dict/words') as fp: 
    words = set(fp.read().split()) 

given_word = 'textbook' 

perms = (permutations(given_word, i) for i in range(4, len(given_word)+1)) 
pwords = (''.join(p) for p in chain(*perms)) 
matches = words.intersection(pwords) 

print matches 

co daje

>>> print matches 
set(['textbook', 'keto', 'obex', 'tote', 'oboe', 'text', 'boot', 'toto', 'took', 'koto', 'bott', 'tobe', 'boke', 'toot', 'book', 'bote', 'otto', 'toke', 'toko', 'oket']) 

Answer 4

Tworzenie cały zestaw zasilający, a następnie sprawdzić, czy słownika słowo jest w zestawie (kolejność liter nie ma znaczenia):

powerset = lambda x: powerset(x[1:]) + [x[:1] + y for y in powerset(x[1:])] if x else [x] 

pw = map(lambda x: sorted(x), powerset(given_word)) 
filter(lambda x: sorted(x) in pw, words) 

Answer 5

Poniższe sprawdza tylko każde słowo w słowniku, aby sprawdzić, czy ma odpowiednią długość, a następnie, czy jest to permutacja "podręcznika". Pożyczyłem próbę permutacji od Checking if two strings are permutations of each other in Python , ale zmieniłem ją nieznacznie.

given_word = 'textbook' 

with open('/usr/share/dict/words', 'r') as f: 
    words = [s.strip() for s in f.readlines()] 

matches = [] 
for word in words: 
    if word != given_word and 4 <= len(word) <= len(given_word): 
     if all(word.count(char) <= given_word.count(char) for char in word): 
      matches.append(word) 
print sorted(matches) 

To kończy się niemal natychmiast i daje prawidłowy wynik.

Answer 6

Permutacje stają się bardzo duże dla dłuższych słów. Spróbuj na przykład kontrrewolucyjnego.

Filtrowałbym dyktowanie słów od 4 do len (słowo) (8 dla podręcznika). Następnie chciałbym filtrować za pomocą wyrażenia regularnego "obój" .matka ("[podręcznik] +").

Pozostałe słowa, sortuję i porównuję je z posortowaną wersją Twojego słowa ("beoo", "bekoottx"), przeskakując do następnego indeksu pasującego znaku, aby znaleźć niedopasowane liczby znaków:

("beoo", "bekoottx") 
("eoo", "ekoottx") 
("oo", "koottx") 
("oo", "oottx") 
("o", "ottx") 
("", "ttx") => matched 


("bbo", "bekoottx") 
("bo", "ekoottx") => mismatch 

Ponieważ nie mówię Pythona, zostawiam implementację jako ćwiczenie dla publiczności.