Anagramy

O anagramach

Anagram jest to wyrażenie, które powstało z przestawienia liter innego wyrażenia. Liczba poszczególnych znaków w obu wyrażeniach jest równa. Przykładowo dla wyrazu tok anagramem jest wyraz kot. Choć jest to oczywiste warto zauważyć, że oba wyrażenia mają tyle samo liter. Jeśli warunek identycznej długości nie jest spełniony śmiało można stwierdzić, że nie są to anagramy.

Implementacja

Najprostszy sposób na sprawdzenie czy wyrażenia są anagramy polega na policzeniu ilości każdego ze znaków, a następnie porównania wartości. Takie podejście dla wyrażenia długości n o d różnych znakach wykona 2n + d porównań. Jest to związane z liczeniem znaków w jednym i drugim wyrazie, a następnie porównanie wartości dla każdego znaku. Innymi słowy złożoność czasowa wyniesie wtedy Θ(n + d). Dodatkowo algorytm potrzebuje dwóch dodatkowych tablic zliczających - każda o długości d. Złożoność pamięciowa wyniesie Θ(d).

W podanym rozwiązaniu zakładamy, że wyrażenia to pojedyncze wyrazy o długości nie przekraczającej 32 znaki i złożone tylko z małych liter alfabetu łacińskiego. Na początek zaczniemy od prostej funkcji zliczającej znaki w wyrazie:

1. int* policzZnaki(char* napis){
2.   int d = 'z' - 'a' + 1;
3.   int* lista = new int[d];
4.   for(int i = 0; i < d; i++)
5.     lista[i] = 0;
6.   for(int i = 0; napis[i]; i++)
7.     lista[napis[i] - 'a']++;
8.   return lista;
9. }

(1.) Funkcja policzZnaki() zwraca tablicę liczb całkowitych, która będzie zawierać ilości kolejnych znaków (od a do z). Wymaganym argumentem jest napis czyli wyraz do przeanalizowania. (2.) Wyliczamy ile unikalnych mamy znaków. (3.) Alokujemy pamięć pod tablicę pomocniczą. (4., 5.) Zerujemy wszystkie liczniki w tablicy lista. (6.) Dla każdego znaku w napisie (7.) zwiększamy odpowiedni licznik. (8.) Na koniec zwracamy lista.

Mają już funkcję zliczającą elementy na liście możemy przejść do właściwej funkcji anagramy():

1. bool anagramy(char* napis1, char* napis2){
2.   if(strlen(napis1) != strlen(napis2))
3.     return false;
4.   int* lista1 = policzZnaki(napis1);
5.   int* lista2 = policzZnaki(napis2);
6.   int d = 'z' - 'a' + 1;
7.   int anagram = true;
8.   for(int i = 0; i < d; i++){
9.     if(lista1[i] != lista2[i]){
10.       anagram = false;
11.       break;
12.     }
13.   }
14.   delete[] lista1, lista2;
15.   return anagram;
16. }

(1.) Funkcja przyjmujemy dwa argumenty napis1 i napis2 - napisy, które mamy zbadać czy są anagramami. Wynikiem końcowym jest wartość logiczna. (2.) Sprawdzamy czy długości wyrazów są takie same. (3.) Jeśli nie to zwracamy automatycznie fałsz. (4., 5.) Jeśli jednak są tej samej długości to dla każdego napisu wyliczamy tablicę ilości jego znaków. (6.) Obliczamy długość tablicy znaków. (7.) Zakładamy, że są to anagramy. (8.) Porównuje odpowiednie liczniki na obu listach. (9.) Jeśli są różne to: (10.) ustawiamy wynik anagram na fałsz i (11.) przerywamy funkcję for. (13.) Przed zwróceniem wyniku zwalniamy pamięć użytą pod listy pomocnicze i (14.) kończymy zwracając wartość anagram.

Szybsza implementacja

Implementację można zoptymalizować. Nie ma potrzeby deklarować dwóch tablic. Możemy użyć jednej i jeśli w pierwszym wyrazie wystąpi j-ty znak to zwiększymy j-ty licznik. Jednak jeśli w drugim to licznik zmniejszymy o 1. W ten sposób zużyjemy znacznie mniej pamięci - złożoność wyniesie wtedy rzeczywiście Θ(d):

1. bool anagramy(char* napis1, char* napis2){
2.   if(strlen(napis1) != strlen(napis2))
3.     return false;
4.   int d = 'z' - 'a' + 1;
5.   int* lista = new int[d];
6.   for(int i = 0; i < d; i++)
7.     lista[i] = 0;
8.   for(int i = 0; napis1[i]; i++){
9.     lista[napis1[i] - 'a']++;
10.     lista[napis2[i] - 'a']--;
11.   }
12.   bool anagram = true;
13.   for(int i = 0; i < d; i++){
14.     if(lista[i] != 0){
15.       anagram = false;
16.       break;
17.     }
18.   }
19.   delete[] lista;
20.   return anagram;
21. }

(1.) Nagłówek pozostaje niezmieniony. (2.) Sprawdzamy czy wyrazy są tej samej długości: jeśli nie to (3.) zwracamy fałsz. (4.) Wyliczamy długość tablicy pomocniczej. (5.) Deklarujemy tablicę pomocniczą lista. (6., 7.) Zerujemy liczniki tablic pomocniczej lista. (7.) Dla każdego elementu z napis1 / napis2 (8.) zwiększamy / (9.) zmniejszamy odpowiedni licznik. (11.) Zakładamy, że napisy są anagramami. (12.) Następnie dla każdego elementu na liście pomocniczej: (13.) sprawdzamy tym razem czy i-ty element jest różny od zera. Jest to warunek, który stwierdza, że napisy nie są anagramami. Wtedy postępujemy jak w poprzedniej implementacji. (20.) Zwalniamy pamięć zarezerwowaną pod listę pomocniczą i (21.) zwracamy wynik.

Wolniej, ale praktycznie bez zużycia pamięci

Obie poprzednie implementacje są odpowiednie kiedy mamy małą ilość znaków. Jednak w przypadku większej ilości różnych znaków możemy zużywać niepotrzebnie duże ilości pamięci. Istnieje możliwość uniezależnienia zależności złożoności czasowej i pamięciowej tylko od długości napisów. W tym celu zmodyfikujemy pobrane napisy - wszystkie znaki na liście posortujemy. W zależności od wybranego sortowania możemy uzyskać długi czas obliczeń przy minimalnym wykorzystaniu pamięci. Przykładowo dla sortowania bąbelkowego wykonamy dwa razy n² porównań plus n porównań czyli uzyskamy złożoność czasową rzędu Θ(n²). Jednak patrząc na to z drugiej strony to nie musimy deklarować dodatkowej tablicy czyli złożoność czasowa wyniesie zaledwie Θ(1):

1. bool anagramy(char* napis1, char* napis2){
2.   if(strlen(napis1) != strlen(napis2))
3.     return false;
4.   sortuj(napis1, strlen(napis1));
5.   sortuj(napis2, strlen(napis2));
6.   bool anagram = true;
7.   for(int i = 0; napis1[i]; i++){
8.     if(napis1[i] != napis2[i]){
9.       return false;
10.     }
11.   }
12. }

(1.) Zachowujemy nagłówek funkcji jak również sprawdzenie (2., 3.) czy napisy mają tą samą długość. Kolejny krok polega na (4., 5.) posortowaniu każdego napisu. (6.) Następnie dla każdej pary znaków dwóch napisów (7.) sprawdzamy czy znaki są takie same. Jeśli nie to (8.) zwracamy fałsz. Jeśli pętli nie przerwiemy ani razu to (11.) zwracamy prawdę.

Testowanie funkcji

Poniższa funkcja main() poprosi użytkownika o wprowadzenie dwóch ciągów znaków, a następnie wypisze na ekran czy dane napisy mogą być anagramami.

1. int main () {
2.   char* napis1 = new char[32];
3.   char* napis2 = new char[32];
4.   cin >> napis1 >> napis2;
5.   cout << (anagramy(napis1, napis2) ? "TAK" : "NIE") << endl;
6.   delete[] napis1, napis2;
7.   system("pause");
8.   return 0;
9. }

• Kod źródłowy Implementacja
• Kod źródłowy Szybsza implementacja
• Kod źródłowy Wolniej, ale bez zużycia pamięci