Anagramy – definicje i sposób analizowania

Prostym sposobem sprawdzenia, czy dwa wyrazy są anagramamianagramanagramami, jest próba ułożenia wszystkich liter składających się na jeden wyraz w taki sposób, aby otrzymać drugie słowo. Jeżeli próba zakończy się powodzeniem, uzyskujemy pewność, że sprawdzane wyrazy są anagramami.

Wykorzystując przedstawioną metodę sprawdź, czy w zapisanych niżej parach jeden wyraz jest anagramem drugiego:

• wektor – wtorek

• makrela – reklama

• łoś – stolik

• bryka – rybak

Trzy spośród czterech podanych par wyrazów są anagramami. Nie dotyczy to tylko wyrazów „łoś” i „stolik”. W przypadku tej właśnie pary od razu stwierdzimy, że jeden wyraz nie może być anagramem drugiego. Powód jest oczywisty: liczba liter w obu słowach jest różna. Nie ma znaczenia, w jaki sposób będziemy je przestawiać – na pewno nie uda nam się przekształcić jednego wyrazu w drugi.

Słowa będące anagramami zawierają taką samą liczbę identycznych liter. Wykorzystamy to spostrzeżenie podczas projektowania algorytmu pozwalającego sprawdzić, czy dwa wyrazy są anagramami.

Anagramami mogą być nie tylko pary wyrazów, ale także pary zdań. Muszą one spełniać te same warunki co słowa, jednak dwa zdania są anagramami nawet wtedy, gdy liczba składających się na nie wyrazów jest inna. Jest to istotne, ponieważ oznacza, że dwa ciągi znaków mogą zawierać różną liczbę spacji, a zarazem być anagramami.

Algorytm do analizowania anagramów: krok 1

Napiszmy algorytm pozwalający sprawdzić, czy dwa wyrazy są anagramami. Wiemy już, że aby tak było, słowa muszą mieć identyczną długość.

Sprawdzimy to od razu – gdyby okazało się, że wyrazy zawierają różną liczbę znaków, na pewno nie są anagramami:

pierwszyWyraz = "arbuz"
drugiWyraz = "kiwi"

jeżeli długość(pierwszyWyraz) != długość(drugiWyraz) wykonaj:
	wypisz "Słowa nie są anagramem"
	zakończ program

Zwróć uwagę na linię numer 4. Została w niej zapisana instrukcja warunkowa, która pozwala wykluczyć słowa o różnej długości.

Na razie nie wiemy jednak jak sprawdzić, czy dwa wyrazy o identycznej długości są anagramami. Wiemy natomiast, że anagramy zawierają tę samą liczbę tych samych liter. Wykorzystajmy tę cechę anagramów.

Algorytm do analizowania anagramów: krok 2

Posłużymy się parą wyrazów „arbuz – burza”. Posortujemy alfabetycznie litery w obydwu słowach:

arbuz → abruz

burza → abruz

Wynikiem sortowania jest przekształcenie obydwu wyrazów w dwa ciągi znaków (liter) ułożonych w porządku alfabetycznym. Jeżeli – tak jak w naszym przykładzie – sekwencje te są są identyczne, mamy pewność, że dwa sprawdzane wyrazy są anagramami.

Dopiszmy zatem do algorytmu instrukcje sortowania i porównywania otrzymanych ciągów liter:

pierwszyWyraz = "arbuz"
drugiWyraz = "kiwi"

jeżeli długość(pierwszyWyraz) != długość(drugiWyraz) to
	wypisz "Słowa nie są anagramem"
	zakończ program
  
jeżeli sortujAlfabetycznie(pierwszyWyraz) == sortujAlfabetycznie(drugiWyraz) wykonaj:
	wypisz "Słowa są anagramem"
	zakończ program

Ponieważ w czasie bieżącej lekcji nie zajmujemy się algorytmami sortującymialgorytm sortującyalgorytmami sortującymi, nie będziemy pisać własnej implementacji mechanizmu sortowania alfabetycznego. W pseudokodzie użyliśmy funkcji sortujAlfabetycznie(), która jako argument przyjmuje badany wyraz, a jako wynik zwraca ciąg liter posortowanych w kolejności alfabetycznej.

Nasz algorytm jest już prawie gotowy. Aby jednak można go było wykorzystać nie tylko w przypadku wyrazów, ale również całych zdań, musimy wprowadzić kilka usprawnień.

Różnica między sprawdzaniem wyrazów a sprawdzaniem zdań polega na tym, że w zdaniach pojawiają się spacje (a także znaki interpunkcyjne, ale w tej implementacji algorytmu je pominiemy). Spacje nie mają wpływu na to, czy dwa zdania są anagramami. Możemy więc usunąć takie znaki. Wykorzystamy funkcję usunSpacje(), która zwraca przekazany jej ciąg wyrazów pozbawiony znaków spacji.

Nadamy ponadto inne nazwy używanym dotychczas zmiennym pierwszyWyraz i drugiWyraz. Zastąpią je zmienne pierwszyCiagZnakow i drugiCiagZnakow – takie nazwy opisują zarówno wyrazy, jak i całe zdania. Jest to modyfikacja czysto kosmetyczna, ale mimo to warta zastosowania.

Oto zapis gotowego algorytmu:

pierwszyCiagZnakow = usunSpacje("arbuz")
drugiCiagZnakow = usunSpacje("kiwi")

jeżeli długość(pierwszyCiagZnakow) != długość(drugiCiagZnakow) wykonaj:
	wypisz "Słowa nie są anagramem"
	zakończ program
  
jeżeli sortujAlfabetycznie(pierwszyCiagZnakow) == sortujAlfabetycznie(drugiCiagZnakow) wykonaj:
	wypisz "Słowa są anagramem"
	zakończ program

Sortowanie alfabetyczne i porównywanie otrzymanych ciągów liter nie jest jedyną metodą sprawdzenia, czy dwa zdania lub wyrazy są anagramami. W dalszej części lekcji poznasz implementację innego algorytmu. Zanim do niej przejdziesz, przypomnij sobie jednak, czym jest kod ASCIIkod ASCIIkod ASCII. Wiedza ta okaże się bowiem niezbędna podczas omawiania kolejnej metody znajdowania anagramów.

Pozostałe materiały z serii

6,66,6,6,6

P5k3GmTcp

Anagramy w języku C++

Psjk6c4Vn

Anagramy w języku Java

PwfOhQPBy

Anagramy w języku Python

PD7egCT2D

Anagramy – zadania maturalne

Słownik