Python ćwiczenie - anagram

W tym artykule sprawdzamy, czy wyrazy są anagramami. Wykorzystamy dwa podejścia, z których jedno obejmuje konwersję do listy i sortowanie oraz porównywanie, drugie zaś to popularne w różnych zadaniach algorytmicznych podejście „frequency counter”.

Wyraz jest anagramem innego wyrazu, jeżeli składa się z tych samych liter w takiej samej liczbie, ale różnej kolejności.

Wyrazy „kara” i „arak” są przykładami anagramów, ponieważ są utworzone z tych samych liter i w takiej samej ilości – np. litera a występuje 2 razy, pozostałe litery 1 raz.

Podejście pierwsze – sortowanie

Napisy można zamieniać na listy. Listy można sortować.

word1 = "arak"
word2 = "kara"

def is_anagram(str1, str2):
    arr1 = sorted(list(str1))
    arr2 = sorted(list(str2))
    print(arr1, arr2)

is_anagram(word1, word2)
#['a', 'a', 'k', 'r'] ['a', 'a', 'k', 'r']

Jak widać, te napisy zamienione na listy i posortowane wyglądają identycznie. Co jeszcze można w języku Python robić?

Zamieniać listy na napisy, napisy zaś porównywać ze sobą za jednym razem (zamiast stosować pętlę – listy są mutowalne, napisy nie i można je porównywać).

word1 = "arak"
word2 = "kara"

def is_anagram(str1, str2):
    first = "".join(sorted(list(str1)))
    second = "".join(sorted(list(str2)))
    print(first, second)

is_anagram(word1, word2)
#aakr aakr

Posortowaliśmy napisy, jesteśmy blisko celu. Teraz jedyne, co trzeba zrobić, to te napisy porównać:

word1 = "arak"
word2 = "kara"


def is_anagram(str1, str2):
    first = "".join(sorted(list(str1)))
    second = "".join(sorted(list(str2)))
    return first == second

print(is_anagram(word1, word2))
#True

Możemy jeszcze naszą funkcję udoskonalić tak, aby wielkość liter nie miała znaczenia:

word1 = "Arak"
word2 = "kaRA"


def is_anagram(str1, str2):
    first = "".join(sorted(list(str1.lower())))
    second = "".join(sorted(list(str2.lower())))
    return first == second

print(is_anagram(word1, word2))
#True

Mogłoby nas kusić, aby lower() zastosować dopiero w returnie, ale nie – musimy to zrobić przed posortowaniem. Sortowanie inaczej bowiem traktuje małe i wielkie litery.

Podejście drugie – frequency counter

Rzućmy okiem na tę funkcję, która będzie naszą funkcją pomocniczą:

def count_elements(arr):
    element_count = {}
    for element in arr:
        if element in element_count:
            element_count[element] += 1
        else:
            element_count[element] = 1
    return element_count


arr = [1, 2, 3, 4, 1, 2, 1]
print(count_elements(arr))  
# {1: 3, 2: 2, 3: 1, 4: 1}

Prawie dobrze, działa na tablicach liczb, zwraca element w kluczu i ilość wystąpień w wartości.

U nas będzie ona działać na napisach, ponadto musi traktować małe litery jak wielkie:

word1 = "Arak"
word2 = "kaRA"


def count_elements(word):
    element_count = {}
    for element in word.lower():
        if element in element_count:
            element_count[element] += 1
        else:
            element_count[element] = 1
    return element_count


print(count_elements(word1))
print(count_elements(word2))
# {'a': 2, 'r': 1, 'k': 1}
# {'k': 1, 'a': 2, 'r': 1}

Teraz, gdy wiemy jak już ta nasza funkcja count_elements działa najwyższy czas napisać funkcję główną, która będzie sprawdzać, czy wyrazy są anagramami.

def is_anagram(word1, word2):
    counter1 = count_elements(word1)
    counter2 = count_elements(word2)
    for key in counter1.keys():
        if key not in counter2.keys():
            return False
        if counter1[key] != counter2[key]:
            return False
    return True

Pakujemy do słowników litery i ich ilość wystąpień w obu wyrazach. Przechodzimy po kluczach z licznika pierwszego w pętli for.

Jeżeli w słowniku drugim nie ma takiego samego klucza, to oznacza, że litera z wyrazu pierwszego w drugim wyrazie w ogóle nie występuje – warunek oblany.

Jeżeli litera występuje w obu wyrazach, warto sprawdzić, czy występuje taką samą ilość razy – jeżeli nie, warunek oblany.

Potem zwracamy True. Zobaczmy, czy nasza funkcja działa:

word1 = "Arak"
word2 = "kaRA"


def count_elements(word):
    element_count = {}
    for element in word.lower():
        if element in element_count:
            element_count[element] += 1
        else:
            element_count[element] = 1
    return element_count


def is_anagram(word1, word2):
    counter1 = count_elements(word1)
    counter2 = count_elements(word2)
    for key in counter1.keys():
        if key not in counter2.keys():
            return False
        if counter1[key] != counter2[key]:
            return False
    return True

print(is_anagram(word1, word2))
#True

To podejście do rozwiązywania problemów programiści nazywają „frequency counter” i często występuje w najróżniejszych zadaniach algorytmicznych, dlatego warto znać.

Natomiast oba podejścia są zasadniczo dobre i pokazują naszą znajomość języka Python.

Wyzwanie – czy ta funkcja działa poprawnie?

Zobaczmy na tę funkcję. Wyzwanie polega na sprawdzeniu, czy rzeczywiście działa ona poprawnie i sprawdza, czy wyrazy są anagramami. Jeżeli nie – na wskazaniu gdzie leży problem i jak go rozwiązać.

w1 = "arak"
w2 = "kara"


def sus_anagram_check(word1, word2):
    if len(word1) != len(word2):
        return False
    return len(set(word1)) == len(set(word2))

print(sus_anagram_check(w1, w2))
#True

Wydaje się działać. Co robi ta funkcja? Sprawdza dwie rzeczy:

Sprawdza, czy wyrazy są jednakowej długości. Jeżeli nie – fałsz
Sprawdza, czy unikalne wartości występują odpowiednią ilość razy

Czy ta funkcja sprawdza, czy wyrazy są anagramami?

Nie.

w1 = "arak"
w2 = "okki"


def sus_anagram_check(word1, word2):
    if len(word1) != len(word2):
        return False
    return len(set(word1)) == len(set(word2))

print(sus_anagram_check(w1, w2))
#True

Tutaj mamy dwa wyrazy. Oba tej samej długości, oba mają taką samą liczbę unikalnych elementów.

Czy poniższa funkcja jest rozwiązaniem problemu?

def sus_anagram_check(word1, word2):
    if len(word1) != len(word2):
        return False
    return set(word1) == set(word2)

print(sus_anagram_check("arak", "okki"))
#False
print(sus_anagram_check("arak", "kara"))
#True

Należy się zastanowić, co ta funkcja robi. Po pierwsze, sprawdza, czy długość wyrazów jest taka sama. Po drugie, sprawdza, czy wyrazy zawierają takie same unikalne elementy.

Niestety ta funkcja nie jest dobra – nie sprawdza, czy te same elementy występują w takiej samej ilości w obu napisach:

def sus_anagram_check(word1, word2):
    if len(word1) != len(word2):
        return False
    return set(word1) == set(word2)

print(sus_anagram_check("arak", "karr"))
#True

Mamy tutaj dwa wyrazy jednakowej długości – „arak” i „karr”. Oba wyrazy mają jednakowe unikalne elementy – „a, k oraz r”. Nie są jednak anagramami – występują w innej ilości.

Czy da się tę funkcję naprawić?

Teoretycznie tak, w praktyce byłoby to użycie sposobu z sortowaniem. Naprawienie problemu wyeliminowałoby potrzebę użycia zbioru (set) w pierwszym momencie. Mielibyśmy w zasadzie podejście numer 1 z mniej czytelnym kodem.

Nie wszystko, co wydaje się pomysłem na świetne i podstępne rozwiązanie, musi działać.

Właśnie dlatego testujemy nasz kod i dobieramy funkcje, logikę oraz struktury danych według potrzeb.

Python ćwiczenie – anagram

Podejście pierwsze – sortowanie

Podejście drugie – frequency counter

Wyzwanie – czy ta funkcja działa poprawnie?