Prosta Permutacja

Wstęp

Do utworzenia wszystkich możliwych permutacji pewnego ciągu można zastosować algorytm z nawrotami (tzw. backtracking). Najprostsza implementacja wypisuje permutacje nawet jeśli się duplikują. W tym artykule zostanie dokładnie opisane jak napisać algorytm do generowania permutacji pewnego wyrażenia.

Opis algorytmu

Generator permutacji dla wyrażenia 123 powinien zwrócić następujące wartości (w dowolnej kolejności):

1. 123
2. 132
3. 213
4. 231
5. 321
6. 312

Algorytm wykorzystujący algorytm z nawrotami działa następująco: wybierz kolejny, dotychczas niewybrany znak i umieść go na kolejnej pozycji. Następnie wywołaj funkcję do permutowania z nowoutworzonym słowem. Powtórz to dla każdego niewybranego znaku. Rekurencyjne wywoływanie funkcji kończy się, gdy wszystkie znaki słowa zostały ustalone.

Przykład

Prześledźmy działanie algorytmu dla wyrażenia "ABC".

Kontynuując ten algorytm wszystkie możliwe permutacje zostaną znalezione.

Uwagi

Podczas działania tego algorytmu nie jest sprawdzane czy dana permutacja już wcześniej wystąpiła. Oznacza to, że niektóre permutacje mogą się powtarzać jeśli jakiś znak występuje więcej niż jeden raz.

Złożoność

Podczas wykonywania tego algorytmu sprawdzane są wszystkie możliwe kombinacje, więc złożoność wynosi O(n·n!). Zakładając, że wszystkie elementy wyrażenia są unikalne nie istnieje algorytm o lepszej złożoności niż wspomniana.

Implementacja

Funkcja permutuj() przyjmuje dwa argumenty: slowo - tekst dla którego mają zostać wygenerowane permutacje oraz opcjonalny argument poz ile pierwszych znaków tekstu pominąć. W celu permutacji całego tekstu należy go ustawić na 0, a najlepiej skorzystać z domyślnej wartości.

1. void permutuj(string slowo, int poz = 0) {
2.   if (poz == slowo.size()) {
3.     cout << slowo << endl;
4.   } else {
5.     for (int i = poz; i < slowo.size(); i++) {
6.       swap(slowo[i], slowo[poz]);
7.       permutuj(slowo, poz + 1);
8.       swap(slowo[i], slowo[poz]);
9.     }
10.   }
11. }

Algorytm rekurencyjnie wybiera znak do ustawienia na pozycji poz, a następnie rekurencyjnie przechodzi do ustawienia następnego znaku. Zakłada się, że znaki o indeksie mniejszym od poz zostały już wybrane, a wszystkie znaki "wolne" są od indeksu poz do końca tekstu. Wszystkie znalezione permutacje są wypisywane od razu na konsolę.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższej fragmentu, który wczytuje wyrażenie, a następnie wypisuje wszystkie permutacje.

1. int main () {
2.   string slowo;
3.   cout << "Podaj wyrazenie:\n slowo = ";
4.   getline(cin, slowo);
5.   permutuj(slowo);
6.   system("pause");
7.   return 0;
8. }

• Kod źródłowy Implementacja