Przeczytaj

Anagram jest słowem lub wyrażeniem, które powstaje w wyniku przestawienia liter lub sylab innego wyrazu lub innej frazy. Przykładami anagramów są: 'krab' = 'brak' = 'bark'.

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 ASCIIASCIItablicy ASCII.
narodowe znaki diakrytyczneznaki diakrytyczneznaki 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 ASCIIASCIItablicy ASCII,
narodowe znaki diakrytyczneznaki diakrytyczneznaki 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 'ż')

Wprowadzenie

Schemat interaktywny

Generowanie anagramów

Słownik