Permutacje

                Permutacją pewnego n-elementowego zbioru jest każdy n-wyrazowy ciąg zawierający wszystkie elementy tego zbioru. Mówiąc krótko: permutacja to każde możliwe uporządkowanie wszystkich elementów zbioru. Od dobrego algorytmu generującego wszystkie możliwe kombinacje oczekujemy, że:

·         generacja permutacji będzie odbywała się w jakiejś sensownej kolejności

·         dobre działanie w przypadku multizbioru tzn. nie będą się powtarzały permutacje w przypadku gdy niektóre elementy będą się powtarzać

·         generacja permutacji odbywała się w możliwie najkrótszym czasie

                Algorytm będzie spełniał te wymagania gdy kolejne permutacje będą generowane w porządku leksykograficznym. Przykładem porządku leksykograficznego jest słownik - każde słowo jest zbudowane z n liter które mają określony, alfabetyczny porządek - a, b, c, d,e..., czyli słowo które zaczyna się na literę E wystąpi przed słowem na literę N. Jeżeli dwa słowa zaczynają się na tą samą literę - patrzymy na kolejną w ciągu i porównujemy te litery oceniając które słowo powinno być pierwsze.

                Aby zapewnić odpowiednią generację permutacji wejściowy ciąg elementów musi być posortowany niemalejąco - warunek ten zapewnia generację leksykograficzną (ciąg wejściowy z faktu takiego ustawienia jest uważany za najmniejszy - czyli w pierwszy) oraz poprawne działanie algorytmu. W każdym kroku algorytmu wybieramy możliwie najdalszy element bieżącej permutacji i "powiększamy" go. Powiększamy go poprzez zamianę miejsc z możliwie najmniejszym, większym elementem od niego. Jak w optymalny sposób znaleźć te elementy? Otóż każdą permutację analizować będziemy do końca i szukać będziemy elementu mniejszego od jego poprzednika. Jeżeli znaleźć takiego elementu się nie uda - oznacza to ciąg posortowany nierosnąco i koniec generacji. Znaleziony element możemy uznać za możliwie najdalszy ponieważ możemy go zamienić z chociażby elementem poprzednim oraz nie można go zamienić z żadnym większym elementem występującym dalej. Następnie zamieniamy miejscami wybrany element z najmniejszym elementem położonym dalej, który jest od niego większy. Na koniec musimy uzyskać resztę permutacji posortowaną niemalejąco - wystarczy odwrócić jej kolejność.

                Aby rozjaśnić nieco sposób generacji rozważmy następujący przykład:

Aktualna permutacja:

8842811321

Znajdujemy najdłuższy, rosnący ciąg elementów patrząc od końca:

8842811 321

Możliwie najdalszy element to 1 - jest to pierwszy element mniejszy od poprzednika:

8842811 321

Następnie znajdujemy pierwszy element większy od elementu najdalszego licząc od końca ciągu:

8842811 321

Zamieniamy te dwa elementy miejscami:

8842812 311

Odwracamy kolejność reszty ciągu:

8842812 113

I w ten oto sposób otrzymaliśmy kolejną permutację ciągu.

Implementacja

void permutation(int n, int[] arr)

        {

            int i = 0;

            while (true)

            {

                printArray(arr, n + 1);

                i = n - 1;

                while (arr[i] >= arr[i + 1]) i--;

                if (i == 0) break;

                int j = n;

                while (arr[i] >= arr[j]) j--;

                swap(arr, i, j);

                int r = n; int s = i + 1;

                while (r > s)

                {

                    swap(arr, r, s);

                    r--;

                    s++;

                }

            }

        }

                Argumenty wejściowe to: liczba elementów w tablicy oraz tablica z elementami posortowanymi niemalejąco. Zmienna pomocnicza i odpowiada za przechowywanie indeksu elementu najdalszego, natomiast zmienna j elementu do zamiany. Zgodnie z algorytmem najpierw wyszukiwany jest element najdalszy i sprawdzamy czy generacja dobiegła końca. Dalej poszukiwany jest zamiennik oraz następuje zamiana tych elementów. Ostatnia pętla zajmuje się odwróceniem kolejności reszty ciągu.

                Uwaga, ze względu na charakter tego algorytmu - musi on wyprodukować każdą możliwą kombinację z ciągu wejściowego - czas jego wykonania może być ekstremalnie długi. W tabeli poniżej znajduje się parę przykładowych czasów:

Długość ciągu	5	9	12	13
Czas	<<1ms	12ms	11s	148s

                Dla zainteresowanych: ciekawym sposobem generowania wszystkich sekwencji danego zbioru elementów jest algorytm Steinhaus–Johnson–Trotter'a.