Anagramy - algorytm i implementacja w C++, Java, Python

Kolejnym z algorytmów, który warto znać podchodząc do matury z informatyki jest algorytm sprawdzający, czy dwa napisy lub wyrazy są anagramami. Znając taki algorytm już na starcie możemy oszczędzić nieco maturalnego czasu, a ten jest na wagę złota. Algorytm na anagramy lepiej, więc poznać zawczasu, aby przypadkiem się na nim nie potknąć.

Czym są anagramy?

Anagramy są słowami lub zdaniami, które tworzy się przestawiając znaki innego wyrazu. Anagramy zawsze więc mają taką samą długość i składają się z tych samych znaków.  Wiele osób spotyka się ze słowami będącymi anagramami nawet nie wiedząc, że tak się poprawnie je określa. Przykładowymi anagramami są:

• "matura" i "trauma"
• "arbuz" i "burza"
• "Tom Marvolo Riddle" i "I am Lord Voldemort"
• "101101" i  "111001" - liczby też mogą być anagramami

Jak widać wszystkie te wyrazy można ułożyć przestawiając znaki drugiego wyrazu z pary.

Jak sprawdzić, czy dwa wyrazy są anagramami?

Chcąc sprawdzić, czy dwa wyrazy to anagramy, już na samym początku należy porównać ich długość. Jeśli długości są różne to wyrazy nie są swoimi anagramami. Krótka piłka. Następnie oba wyrazy sortujemy alfabetycznie (bądź od najmniejszej do największej jeśli mowa o liczbach). Jeśli po posortowaniu wyrazy wyglądają identycznie to znaczy, że są anagramami.

Weźmy na przykład słowa "trauma" i "matura". Oba są długie na 5 liter. Po posortowaniu oba będą wyglądały w ten sposób: "aamrtu", więc są anagramami.

Tak za pomocą pseudokodu można przedstawić algorytm sprawdzający, czy dwa słowa są anagramami.

wczytaj wartość pierwszego napisu

wczytaj wartość drugiego napisu

jeżeli napisy są różnej długości

                zwróć fałsz

jeżeli napisy są równej długości

                posortuj pierwszy napis

                posortuj drugi napis

                jeżeli posortowane napisy są sobie równe

                               zwróć prawdę

                w przeciwnym wypadku

                               zwróć fałsz

Tak wygląda schemat blokowy tego algorytmu:

Program sprawdzający, czy dwa słowa są anagramami.

Program pisałem w oparciu o algorytm sortowania bąbelkowego, które już omawiałem. Leciutko przerobiłem program z wpisu o tej metodzie sortowania, aby teraz operował na stringach.

Funkcje pobierają dwa stringi i zwracają true (1), jeśli są anagramami oraz false (0), jeżeli nie są.

C++

//program sprawdzający, czy dwa słowa są anagramami
//Kosiński Łukasz
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

void sortuj(string &napis)
{
    
    for(int i=0, zamiany=1; i<napis.length()-1 && zamiany!=0; i++)
    {
        zamiany=0;
        for(int j=0; j<napis.length()-1; j++)
            if(napis[j]>napis[j+1])
            {
                swap(napis[j], napis[j+1]);
                zamiany++;	
            } 
    }
    
}
string formatuj(string s){ //funkcja zamieniajaca na male litery i usuwajaca biale znaki
    string s1 = "";
    for(auto& c : s){
        if(c == ' '){
            continue;
        }
        s1 += (char)tolower(c);
    }
    return s1;
}
bool czy_anagramy(string napis1, string napis2)
{
    if(napis1.length()!=napis2.length()) return false;
    
    sortuj(napis1);
    sortuj(napis2);
    
    if(napis1==napis2) return true;
    else 
        return false;
    
}

int main()
{
    
    string a, b;
    cout << "Podaj pierwszy napis: ";
    getline(cin, a);
    cout << "Podaj drugi napis: ";
    getline(cin, b);
    a = formatuj(a);
    b = formatuj(b);
    cout << czy_anagramy(a, b) << endl;// funkcja zwróci 1 jeśli napisy są anagramami
    //a 0 jeśli nie są
    
    
    system("pause");
    return 0;
}

Java

package matura;

import java.util.Scanner;

public class Main {
	
	
	public static String sortWord(String s) { //tworzymy metodę sortującą znaki w słowie - korzystamy tutaj z sortowania bąbelkowego
		char[] characters = s.toCharArray();
		
		for(int i = 0, changes = 1; i < characters.length-1  && changes != 0 ; i++) {
			changes = 0;
			for(int j = 0; j < characters.length-1; j++) {
				if(characters[j] > characters[j+1]) {
					char pom = characters[j+1];
					characters[j+1] = characters[j];
					characters[j] = pom;
					changes++;
				}
			}
		}
		System.out.println(new String(characters));
		return new String(characters);
	}
	
	public static boolean czyAnagramy(String x, String y) {
		if(x.length() != y.length()) { // jeżeli słowa nie są tej samej długości, to na pewno nie są anagramami
			return false;
		}
		return sortWord(x).equals(sortWord(y)); //zwracamy, czy posortowane wyrazy wygladaja tak samo
	}
	public static void main(String[] args) { 
		Scanner sc = new Scanner(System.in); // tworzymy instancję Scanner'a - będzie on pobierał słowa od użytkownika
		System.out.println("Program sprawdzający czy podane wyrazy są anagramami.");
		System.out.println("Podaj pierwsze słowo:");
		String s1 = sc.nextLine().toLowerCase().replaceAll(" ", ""); // pobieramy słowo od użytkownika, jednocześnie zamieniając wszystko na małe litery i pozbywając się spacji
		System.out.println("Podaj drugie słowo:");
		String s2 = sc.nextLine().toLowerCase().replaceAll(" ", ""); // pobieramy słowo od użytkownika, jednocześnie zamieniając wszystko na małe litery i pozbywając się spacji
		System.out.println("Podane wyrazy " + (czyAnagramy(s1, s2) ? "są" : "nie są") + " anagramami");
		sc.close(); //zwalniamy zasoby
		
		
	}
		
		
		
		
	
	
}

Python

def sortujSlowo(slowo): #definujemy funkcje sorutjaca slowo - wykorzystujemy tutaj sortowanie babelkowe
    s = list(slowo) #poniewaz w Pythonie nie da sie modyfikowac stringa jako tablicy, potrzebujemy zapisac go jako liste
    zmian = 1
    for i in range(len(s) - 1):
        if zmian == 0:
            break
        zmian = 0
        for j in range(len(s)  - 1):
            if s[j] > s[j + 1]:
                s[j], s[j + 1] = s[j + 1], s[j]
                zmian += 1
    return s
def czyAnagramy(x, y):
    if len(x) != len(y): #jezeli sa roznej dlugosci, to z gory wiadomo ze nie sa anagramami
        return False
    return sortujSlowo(x) == sortujSlowo(y) #w przeciwnym wypadku wystarczy sprawdzic, czy po posortowaniu sa identyczne

print("Program sprawdzajacy czy dwa slowa sa anagramami")
print("Podaj pierwsze slowo")
s1 = input() #pobieramy pierwsze slowo
print("Podaj drugie slowo")
s2 = input() #pobieramy drugie slowo
print("Podane slowa " + ("sa " if(czyAnagramy(s1, s2)) else "nie sa ") + "anagramami")