Problem generowania permutacji polega na wyznaczeniu wszystkich możliwych uporządkowań elementów danego zbioru. Dla zbioru zawierającego 𝑛 różnych elementów istnieje dokładnie 𝑛 ! (silnia) permutacji, co sprawia, że liczba rozwiązań bardzo szybko rośnie wraz z rozmiarem danych.

Problem ten często rozwiązuje się za pomocą rekurencji, ponieważ każdą permutację można zbudować, ustalając jeden element na danej pozycji, a następnie rekurencyjnie generując permutacje pozostałych elementów. W praktyce algorytm polega na wyborze kolejnych elementów, zamianie ich miejscami oraz cofnięciu zmian po zakończeniu danego kroku (tzw. backtracking).

Generowanie permutacji jest nie tylko klasycznym zadaniem algorytmicznym, ale także ćwiczeniem logicznego myślenia, wykorzystywanym m.in. w kombinatoryce, testowaniu oprogramowania, kryptografii czy rozwiązywaniu zagadek logicznych. Ze względu na swoją strukturę problem ten doskonale ilustruje ideę rekurencji i systematycznego przeszukiwania wszystkich możliwych rozwiązań.

Zapis rekurencyjnego algorytmu generowania permutacji w postaci pseudokodu

Dane:

• Dane wejściowe: tablica A o długości n

• Parametr k oznacza aktualną pozycję, na której ustalamy element

procedura PERMUTACJE(A, k, n)
    jeżeli k = n
        wypisz A
    w przeciwnym razie
        dla i od k do n
            zamień A[k] z A[i]
            PERMUTACJE(A, k + 1, n)
            zamień A[k] z A[i]   // cofnięcie zmiany (backtracking)

Zastosowanie algorytmu generowania permutacji:

1. Szyfry przestawieniowe (transpozycyjne) - Jednym z najprostszych historycznych zastosowań permutacji są szyfry przestawieniowe, w których nie zmienia się znaków wiadomości, lecz ich kolejność. 

2. Permutacje jako klucze kryptograficzne - W kryptografii klucz może być permutacją zbioru elementów:

• liter alfabetu (szyfry podstawieniowe),

• bitów w bloku danych,

• pozycji w tablicy.

3. Sieci podstawień i permutacji (SPN)  - Nowoczesne szyfry blokowe (np. AES) wykorzystują permutacje bitów i bajtów jako jeden z podstawowych mechanizmów:

• podstawienie (S‑box) – zmiana wartości,

• permutacja (P‑box) – zmiana położenia bitów.

4.  Kryptanaliza (łamanie szyfrów) - Generowanie permutacji jest także używane w atakach kryptograficznych, np.:

• sprawdzaniu wszystkich możliwych kluczy (brute force),

• testowaniu możliwych przestawień znaków,

• analizie historycznych szyfrów (np. Enigma).