Zdawałoby się, że permutacja to prosta sprawa. Zwykła zmiana kolejności elementów jakiegoś ciągu. Wszystkich możliwych permutacji ciągu n-elementowego jest n! (czyt. n silnia). Załóżmy, że chodzi o ciąg różnych znaków. Permutacji ciągu 3-elementowego (A,B,C) jest 6 i oto one: (A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A). Ok. Napiszmy kawałek kodu, który wygeneruje wszystkie permutacje ciągu znaków i wypisze je na ekran konsoli.

// our sequence of characters
string sequence = "ABC";

// variables aiding us in char[] <-> string conversion
int n = sequence.Length;
char[] chars = new char[n];
string permutation;

// variables necessary for our algorithm
int[] positions = new int[n];
bool[] used = new bool[n];
bool last;

// initialize positions
for (int i = 0; i < n; i++)
    positions[i] = i;

do
{
    // make permutation according to positions
    for (int i = 0; i < n; i++)
        chars[i] = sequence[positions[i]];
    permutation = new string(chars);

    // output it
    Console.WriteLine(permutation);

    // recalculate positions
    last = false;
    int k = n - 2;
    while (k >= 0) {
        if (positions[k] < positions[k + 1]) {
            for (int i = 0; i < n; i++)
                used[i] = false;
            for (int i = 0; i < k; i++)
                used[positions[i]] = true;
            do positions[k]++; while (used[positions[k]]);
            used[positions[k]] = true;
            for (int i = 0; i < n; i++)
                if (!used[i]) positions[++k] = i;
            break;
        } else k--;
    }
    last = (k < 0);
} while (!last);

Pod zmienną sequence możemy podstawić ciąg znaków w zasadzie dowolnej długości. Jak to działa? W tablicy positions przechowujemy liczby od 0 do n-1 (zaczynając od najmniejszej do największej), a następnie zmieniamy im kolejność aż dochodzimy do kolejności całkowicie odwróconej (od największej do najmniejszej) i to jest ostatnia permutacja. Permutacje tak uzyskane są w tzw. naturalnej kolejności. Tak generuje permutacje człowiek, jeśli go o to poprosimy (no dobrze, nie wiem jak inni ludzie, ale tak to robię ja). Każdą następną permutację uzyskujemy na podstawie poprzedniej. W jaki sposób? Szukamy ostatniej pozycji, na której liczba jest mniejsza niż liczba na następnej pozycji. To jest nasze k. Zwiększamy o 1 liczbę na pozycji k dotąd, aż nie będzie ona występować na pozycjach mniejszych od k. Następnie na pozycjach większych od k wpisujemy wszystkie pozostałe liczby (czyli te, które nie występują na pozycjach od 0 do k włącznie) w kolejności rosnącej. I już mamy następną permutację. Jeśli nie jesteśmy w stanie znaleźć nieujemnego k, to znaczy że wszystkie liczby są w kolejności malejącej, czyli mamy ostatnią permutację i algorytm się kończy.

Główna pętla rozpoczyna się w linii 18, a kończy w linii 45. Jedyną rzeczą, jaką zmieniamy pomiędzy kolejnymi wykonaniami tej pętli jest pomocnicza tablica positions. W takich sytuacjach mówimy, że algorytm działa w miejscu [in place]. To cecha najlepszych z algorytmów, bo potrzebują one małą, przewidywalną ilość pamięci. Algorytm ten generuje n! wyników, ale potrzebuje ilość pamięci tylko rzędu n (chyba, że będziemy chcieli wszystkie te wyniki gdzieś zapisać). Złożoność pamięciowa jest zatem liniowa. A co ze złożonością obliczeniową? Nie chce mi się tego liczyć. Zmierzę to.

Na powyższym wykresie jest zmierzony czas podzielony przez n! w zależności od n. Lipa. Spodziewaliśmy się czegoś proporcjonalnego do n!, a mamy proporcjonalne do n razy n!. Nie powinno nas to dziwić, bo w każdym kroku pętli szukamy pozycji k w n-elementowej tablicy. Średnio znajdziemy ją pewnie po n/2 krokach, czyli mamy złożoność O(n*n!). Czy można to poprawić? Tak, żeby powyższy wykres był funkcją stałą, a złożoność była typu O(n!)? Okazuje się, że TAK, ale o tym innym razem.