Anagramy - PY_I_R_W14_M17 Uwaga plagiat - porównujemy teksty.

RLTzsHxpYrS7K

Anagramy są wyrazami, wyrażeniami lub całymi zdaniami, które powstają wskutek przestawienia liter bądź sylab innych wyrazów lub zdań (z wykorzystaniem wszystkich liter wchodzących w skład tekstu oryginalnego). Przykładowymi anagramami są wyrazy „arbuz” i „burza”. Przestawiając litery w słowie „arbuz” ułożymy wyraz „burza” (nie dodając ani nie pomijając żadnego znaku).

Prostym sposobem sprawdzenia, czy dwa wyrazy są anagramami, 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.

Dla zainteresowanych

Więcej informacji o anagramach można znaleźć w serwisach poświęconych grze scrabble.

Przykład 1

W celu sprawdzenia czy różne ciągi znaków są anagramami możemy wykorzystać wbudowaną funkcję Pythona sorted(). Zwraca ona uporządkowaną rosnąco listę elementów obiektu (ciągu znaków), który został jej przekazany jako parametr.

Pamiętajmy o tym, jak działa funkcja sorted():

powtarzające się znaki są prezentowane jako kolejne elementy listy,
kolejność znaków odzwierciedla ich pozycję w tablicy ASCII.
narodowe znaki diakrytyczne są umieszczone za literami alfabetu łacińskiego.
może posiadać parametr reverse, który pozwala zwrócić listę posortowaną w kolejności malejącej, np. sorted("BED", reverse=True) -> "DEB",

Zapiszmy kod, który będzie sprawdzał, czy dwa ciągi znaków są anagramami:

def sprawdz_anagram_slow(slowo1, slowo2):
	return sorted(slowo1) == sorted(slowo2)

print(sprawdz_anagram_slow('bark', 'krab'))
True

print(sprawdz_anagram_slow('bark', 'krat'))
False

Polecenie 1

Bazując na powyższym przykładzie i przykładach z lekcji o palindromach przygotuj taką modyfikację funkcji, aby wielkość znaków w sprawdzanych wyrażeniach nie miała znaczenia.

Przykład 2

Aby sprawdzić, czy zdania są anagramami, postępujemy podobne. Musimy jednak usunąć wszystkie znaki przestankowe (mogą one wpływać na wynik porównania ciągów).

Pamiętajmy o tym, jak działa funkcja sorted():

powtarzające się znaki są prezentowane jako kolejne elementy listy,
kolejność znaków odzwierciedla ich pozycję w tablicy ASCII,
narodowe znaki diakrytyczne są umieszczone za literami alfabetu łacińskiego.
może posiadać parametr reverse, który pozwala zwrócić listę posortowaną w kolejności malejącej, np. sorted("BED", reverse=True) -> "DEB",

Przygotujmy kod, który będzie sprawdzał, czy dwa zdania są anagramami:

def anagram_re(tekst1, tekst2):
	import re

	# zamianiamy znaki przestankowe na "" (nic)
	tekst1 = re.subn(r"[ ;,:.!?]", "", tekst1)
	# przypisujemy pierwszy element z tupli -> str
	tekst1 = tekst1[0]
	# zamieniamy na małe litery cały napis
	tekst1 = tekst1.lower()
	# wersja analogiczna jak powyżej, ale w jednym poleceniu
	tekst2 = re.subn(r"[ ;,:.!?]", "", tekst2)[0].lower()
    
	return sorted(tekst1) == sorted(tekst2)

Generowanie anagramów

Gdy chcemy utworzyć anagram dowolnego słowa, możemy posłużyć się prostym algorytmem:

Słowo zamieniamy w listę znaków, nie korzystając jednak z funkcji sorted() – powinniśmy bowiem zachować kolejność liter.
Z otrzymanej listy wybieramy losowo znak, który będzie kolejną (początkowo pierwszą) literą nowego słowa.
Z listy znaków usuwany wybraną w punkcie 2. literę.
Powtarzamy czynności opisane w punktach 2. i 3. dopóty, dopóki pozostają litery do wylosowania.

Przykład 3

Spróbujmy napisać program, który bazując na powyższym algorytmie utworzy anagram podanego słowa. Posłużymy się pętlą while.

Linia 1. def stworz podkreślnik anagram otwórz nawias okrągły slowo zamknij nawias okrągły dwukropek. Linia 2. from random import randint. Linia 3. lista znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 5. for litera in slowo dwukropek. Linia 6. lista kropka append otwórz nawias okrągły litera zamknij nawias okrągły. Linia 8. anagram znak równości apostrof apostrof. Linia 10. while lista dwukropek. Linia 11. losowana znak równości randint otwórz nawias okrągły 0 przecinek len otwórz nawias okrągły lista zamknij nawias okrągły minus 1 zamknij nawias okrągły. Linia 12. nowa podkreślnik litera znak równości lista otwórz nawias kwadratowy losowana zamknij nawias kwadratowy. Linia 13. del otwórz nawias okrągły lista otwórz nawias kwadratowy losowana zamknij nawias kwadratowy zamknij nawias okrągły. Linia 14. anagram plus znak równości nowa podkreślnik litera. Linia 16. return anagram. Linia 18. kratka kilka przykładowych wywołań. Linia 19. print otwórz nawias okrągły stworz podkreślnik anagram otwórz nawias okrągły apostrof bark apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 20. apostrof karb apostrof. Linia 21. print otwórz nawias okrągły stworz podkreślnik anagram otwórz nawias okrągły apostrof bark apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 22. apostrof akbr apostrof. Linia 23. print otwórz nawias okrągły stworz podkreślnik anagram otwórz nawias okrągły apostrof bark apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 24. apostrof rkba apostrof. Linia 25. print otwórz nawias okrągły stworz podkreślnik anagram otwórz nawias okrągły apostrof bark apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 26. apostrof arbk apostrof. Linia 27. print otwórz nawias okrągły stworz podkreślnik anagram otwórz nawias okrągły apostrof bark apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 28. apostrof rbak apostrof. Linia 29. print otwórz nawias okrągły stworz podkreślnik anagram otwórz nawias okrągły apostrof bark apostrof zamknij nawias okrągły zamknij nawias okrągły. Linia 30. apostrof brak apostrof.

def stworz_anagram(slowo):
	from random import randint
	lista = []

	for litera in slowo:
		lista.append(litera)

	anagram = ''

	while lista:
		losowana = randint(0, len(lista) - 1)
		nowa_litera = lista[losowana]
		del(lista[losowana])
		anagram += nowa_litera

	return anagram

# kilka przykładowych wywołań
print(stworz_anagram('bark'))
'karb'
print(stworz_anagram('bark'))
'akbr'
print(stworz_anagram('bark'))
'rkba'
print(stworz_anagram('bark'))
'arbk'
print(stworz_anagram('bark'))
'rbak'
print(stworz_anagram('bark'))
'brak'

Dla zainteresowanych

Oto inny wariant funkcji generującej anagramy – pokazuje on, jak w Pythonie można zminimalizować ilość kodu:

def stworz_anagram_2(slowo):
	from random import randint
	lista = [litera for litera in slowo]
	anagram = ''

	while lista:
		anagram += lista.pop(randint(0, len(lista) - 1))

	return anagram

# przykładowe wywołania
print(stworz_anagram('bark'))
'rkba'
print(stworz_anagram('bark'))
'arbk'

Już wiesz

Podsumujmy najważniejsze elementy tej lekcji:

funkcja sorted() zwraca posortowano rosnąco listę elementów podanych jako pierwszy parametr,
funkcja sorted() może posiadać parametr reverse, który pozwala zwrócić listę posortowaną w kolejności malejącej, np. sorted("BED", reverse=True) -> "DEB",
metoda L.pop(x) dla elementu L typu list pobiera element o indeksie x i kasuje go z listy.

Słownik

ASCII

(ang. American Standard Code for Information Interchange) pierwotnie siedmiobitowy system kodowania znaków (współcześnie rozszerzony do ośmiu bitów); w oryginalnej wersji kodom z zakresu 0–127 przyporządkowano 26 liter łacińskich, 10 cyfr (0...9) oraz dodatkowe znaki

znaki diakrytyczne

wszystkie symbole (np. kropki, przecinki, dwukropki), które towarzyszą znakowi podstawowemu, zmieniając sposób odczytywania litery (w języku polskim są to np. kropki i kreski umieszczane nad literami 'ś' lub 'ż')

Palindromy w genetyce

Misja: Ćwicz i zwyciężaj

Generowanie anagramów

Słownik