Dana jest lista wyrazów. Zadanie polega na efektywnym pogrupowaniu tak, że w każdej grupie znajdą się anagramy. Zakładamy, że wielkość liter nie ma znaczenia tj. A i a są tą samą literą. Wypisz następnie znalezione grupy. Przetestuj działania napisanego programu.
Podczas rozwiązywania tego zadania należy rozwiązać dwie trudności. Pierwsza z nich dotyczy szybkości porównywania dwóch wyrazów czy są anagramami oraz szybkie grupowania wyrazów. Ten drugi problem może zostać rozwiązany poprzez zastosowanie słownika. Wtedy jest jednak potrzebny unikalny klucz, który będzie wspólny dla anagramów.
Klucz można utworzyć na podstawie wyrazu poprzez posortowanie jego liter. Nie jest to jednak metoda zbyt optymalna, ponieważ wymaga co najmniej O(n·log(n)) operacji. W anagramach kolejność liter nie ma znaczenia, więc przypiszmy każdemu znakowi alfabetu wartość tj. a = 1, b = 2, .., z = 26. Hash dla wyrazu będzie iloczynem podanych wartości dla liter w nim występujących. Przykładowo 'abc' będzie miało wartość 6. Tak samo jak 'acb' czy 'cba'.
Na podstawie obliczonego hasha algorytm będzie wstawiał odpowiednie dane do słownika. Na koniec wystarczy wypisać wartości przypisane do kolejnych kluczy jako oddzielne grupy.
Przyjmując, że na liście znajduje się n wyrazów, a wyszukanie pozycji do jego wstawienia wymaga log(n) porównań (wykorzystując wyszukiwanie binarne) to końcowa złożoność wynosi O(nlog(n)). Ograniczeniem może się okazać pojemność słownika - jeśli każdy wyraz będzie mieć inny hash to pomieszczenie wszystkich razem będzie niemożliwe.
Jak długie wyrazy będzie można grupować? Otóż jeśli przyjmiemy, że długość wyrazu to k to będzie 26k możliwych hashy. Dla takiej wartości potrzebna liczba bitów to: n ≥ log2(26k) = k·log226. Oto tabelka, która określa jak długie wyraz można umieścić w zależności od wybranego rozmiaru danych:
Ile bitów | Długość wyrazu |
---|---|
16 | 3 |
32 | 6 |
64 | 13 |
128 | 27 |
W powyższej tabeli zakładamy, że wyraz składa się z 26 liter alfabetu łacińskiego.
Funkcja Policz() ma za zadanie obliczyć hash dla podanego wyrazu.
Funkcja składa się z pętli, która przechodzi po kolejnych znakach. Kiedy wykryje literę mnoży aktualny wynik przez jej pozycję w alfabecie. Znak jest zamieniany na mały znak, ponieważ znaki mogą mieć różną wielkość.
Funkcja Grupuj() na podstawie podanych wyrazów grupuje je w słowniku. Elementy są grupowane po obliczonym hashu funkcją Policz().
Dla każdego wyrazu obliczany jest hash. Jeśli obliczona wartość nie występuje jako klucz to należy dopisać nowy. W przeciwnym wypadku wystarczy dopisać wyraz na koniec listy pod danym kluczem.
Do przetestowania napisanej funkcji można skorzystać z poniższego kodu. Po zwróceniu wyniku program wypisuje znalezione grupy.