Anagramy w języku polskim

Zastanawialiście się kiedyś, jaka jest najfajniejsza grupa anagramów w języku polskim? Ja też nie, aż do wczoraj ;)

Na wypadek jeżeli ktoś nie wie - anagram to wyraz powstały poprzez zmianę kolejności liter innego wyrazu, np. "kot" i "tok". Anagramy tworzą całe zbiory (klasy równoważności :P) - np. "kot", "tok" i "kto" to jedna klasa.

Zacząć musimy oczywiście od listy wyrazów. Ja wykorzystałem darmowy słownik SJP przystosowany do gier słownych (takich jak Scrabble bądź Literaki): http://www.sjp.pl/slownik/growy/. Ma on 35 MB i zawiera 2,7 miliona słów. Czyli nie powinno być źle :)

Odpalamy swoje wybrane środowisko C++ i do roboty :)

Jednak zanim napiszemy pierwszą parę nawiasów klamrowych warto wymyślić jak odnaleźć nasze klasy równoważności anagramów.

Pierwsze nasuwa się rozwiązanie siłowe - mając wyraz "kot" dokonujemy wszystkich możliwych permutacji i sprawdzamy czy istnieje taki wyraz w słowniku:
kot - jest
kto - jest
okt - nie ma
otk - nie ma
tko - nie ma
tok - jest

Podejście takie nie ma zbyt wielu szans :) Wyraz o n literach ma n! możliwych permutacji. Najdłuższe wyrazy w słowniku mają 15 liter (dłuższych w grach słownych nie można ułożyć) - daje to ok. 1307 miliardów kombinacji - ciut za dużo :). Oczywiście jeżeli powtarzają się litery w wyrazie, to permutacje też się będą powtarzać - dodatkowy problem.

Podejdźmy zatem do problemu inaczej - co oznacza, że słowa są swoimi anagramami? To, że składają się z dokładnie tych samych liter.

Trzeba w takim razie znaleźć jakiś wyznacznik, który będzie taki sam dla wyrazów składających się z dokładnie tych samych liter. Najprostszym rozwiązaniem będzie posortowanie liter w każdym wyrazie :) Wyobraźmy sobie, że nas słownik by wyglądał tak:

...
okt kot
...
okt kto
...
okt tok
...

Jeżeli teraz po prostu posortujemy cały plik, to anagramy ładnie się nam pogrupują:

...
okt kto
okt kto
okt tok
...

Sortowanie literek w wyrazach możemy wykonać następującym programikiem w C++:

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 100;

int main()
{
  char in_word[MAX_SIZE];
  char out_word[MAX_SIZE];
  do {
    cin >> in_word;
    memcpy(out_word, in_word, MAX_SIZE);
    sort(out_word, out_word + strlen(out_word));
    cout << out_word << " " << in_word << endl;
  } while (strlen(in_word) > 0);
  return 0;
}

Następnie plik można posortować systemowym poleceniem sort. I voila!

Właściwie nie "voila", bo można nasz wynik jeszcze ładnie obrobić ;) Poniższy programik pogrupuje wyrazy, które mają przynajmniej jeden anagram w pojedyncze linie:

#include <iostream>

using namespace std;

const int MAX_SIZE = 100;

int main()
{
  char in_word1[MAX_SIZE];
  char in_word2[MAX_SIZE];
  char old_inword1[MAX_SIZE];
  char old_inword2[MAX_SIZE];
  old_inword1[0] = '\0';
  old_inword2[0] = '\0';
  do {
    cin >> in_word1 >> in_word2;
    if (strcmp(in_word1, old_inword1) != 0) { // not equal
      if (old_inword2[0] == '\0') {
        cout << endl;
      }
      memcpy(old_inword1, in_word1, MAX_SIZE);
      memcpy(old_inword2, in_word2, MAX_SIZE);
    } else {
      cout << old_inword2 << " " << in_word2;
      old_inword2[0] = '\0';
    }
  } while (strlen(in_word1) > 0);
  return 0;
}

A ten programik wypisze na początku każdej linii jej długość w formacie "###:" - dzięki temu będziemy mogli łatwo znaleźć długie (czyli ciekawe) grupy anagramów:

#include <iostream>
#include <iomanip>

using namespace std;

const int MAX_SIZE = 200;

int main()
{
  char line[MAX_SIZE];
  do {
    cin.getline(line, MAX_SIZE);
    cout << setw(3) << setfill('0') << strlen(line) << ": " << line << endl;
  } while (strlen(line) > 0);
  return 0;
}

Teraz wystarczy systemowe sort /R, aby posortować w odwrotnej kolejności i naszym oczom ukazują się najciekawsze anagramy w języku polskim :)

ekranowymi: ekworynami, kierowanym, kreowanymi, niekarmowy, niekarowym, niemakrowy, niemarkowy, niemokrawy, nierakowym, okrywaniem, wykarmione

niemarzeniowy: nierozmywanie, nieryzowaniem, niewymierzona, niewymorzenia, niezerowanymi, niezorywaniem, niezrymowanie