Implementacja generatora permutacji w Java

Program rozpoczyna działanie w metodzie main(). Najpierw tworzy tablicę zawierającą liczby od 1 do 6.

public class Permutacje {
    public static void main(String[] args) {
        int[] dane = {1, 2, 3, 4, 5, 6};
    }
}

Następnie przekazuje tę tablicę do metody permutacje() i informuje ją, że układanie ma rozpocząć się od pierwszego miejsca, czyli od indeksu 0.

public class Permutacje {
    public static void main(String[] args) {
        int[] dane = {1, 2, 3, 4, 5, 6};

        permutacje(dane, 0);
    }
}

Metoda permutacje

Funkcja permutacje() tworzy wszystkie możliwe ustawienia liczb znajdujących się w tablicy.

Funkcja otrzymuje dwa argumenty:

    public static void permutacje(int[] lista, int indeks) {
    }

• lista – tablicę zawierającą liczby,

• indeks – numer miejsca w tablicy, które jest obecnie ustalane.

Na początku funkcja jest wywoływana z wartością indeks równą 0. Oznacza to, że program zaczyna od pierwszego miejsca w tablicy.

Funkcja najpierw sprawdza, czy ustalono już wszystkie miejsca w tablicy. Jeżeli indeks jest równy długości tablicy, oznacza to, że powstało kompletne ustawienie liczb.

Program wypisuje wtedy zawartość tablicy:

    public static void permutacje(int[] lista, int indeks) {
        if (indeks == lista.length) {
            for (int liczba : lista) {
                System.out.print(liczba + " ");
            }
            
        }

    }

Każda liczba zostaje wyświetlona w tym samym wierszu. Następnie instrukcja:

System.out.println();

przenosi kursor do nowego wiersza, a polecenie:

return;

kończy bieżące wykonanie funkcji.

Wybieranie elementu na dane miejsce

Jeżeli permutacja nie jest jeszcze gotowa, uruchamiana jest pętla:

    public static void permutacje(int[] lista, int indeks) {
        if (indeks == lista.length) {
            for (int liczba : lista) {
                System.out.print(liczba + " ");
            }

            System.out.println();
            return;
        }

        for (int i = indeks; i <  lista.length; i++) {
            // Zamiana elementów
            int temp = lista[indeks];
            lista[indeks] = lista[i];
            lista[i] = temp;
        }
    }

Pętla sprawdza kolejno wszystkie liczby, które można umieścić na aktualnej pozycji.

Na przykład, gdy indeks ma wartość 0, program wybiera liczbę na pierwsze miejsce. Następnie dla każdej możliwości ustala liczby na kolejnych pozycjach.

Następuje zamiana elementów

 
            int temp = lista[indeks];
            lista[indeks] = lista[i];
            lista[i] = temp;

Aby umieścić wybraną liczbę na odpowiednim miejscu, program zamienia ze sobą dwa elementy tablicy.

Zmienna temp przechowuje chwilowo jedną wartość, aby nie została utracona podczas zamiany.

Przykładowo z tablicy: 1 2 3 po zamianie pierwszego i drugiego elementu może powstać 2 1 3. Następnie wywołana jest funkcja dla kolejnego miejsca

 permutacje(lista, indeks + 1);

Po wykonaniu zamiany funkcja wywołuje samą siebie. Tym razem wartość indeks jest większa o jeden, więc program zaczyna ustalać kolejne miejsce w tablicy.

Takie wywoływanie funkcji przez nią samą nazywamy rekurencją.

Program działa więc etapami: najpierw wybiera liczbę na pierwsze miejsce, potem na drugie, następnie na trzecie i kontynuuje, aż powstanie pełna permutacja.

Po sprawdzeniu jednej możliwości program przywraca wcześniejszy układ liczb. Dzięki temu może wybrać inną liczbę na tym samym miejscu i utworzyć kolejne permutacje.

Funkcja powtarza więc następujący schemat:

wybiera element → zamienia liczby → przechodzi do kolejnej pozycji → wypisuje gotową permutację → cofa zamianę → sprawdza następną możliwość.

W ten sposób tworzy wszystkie możliwe kolejności elementów tablicy.

public class Permutacje {

    public static void permutacje(int[] lista, int indeks) {
        if (indeks == lista.length) {
            for (int liczba : lista) {
                System.out.print(liczba + " ");
            }

            System.out.println();
            return;
        }

        for (int i = indeks; i <  lista.length; i++) {
            // Zamiana elementów
            int temp = lista[indeks];
            lista[indeks] = lista[i];
            lista[i] = temp;

            permutacje(lista, indeks + 1);

            // Cofnięcie zamiany
            temp = lista[indeks];
            lista[indeks] = lista[i];
            lista[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] dane = {1, 2, 3, 4, 5, 6};

        permutacje(dane, 0);
    }
}

Jak działa algorytm:

• Na pierwszej pozycji próbujemy ustawiać kolejno wszystkie 6 elementów.

• Dla każdej takiej decyzji rekurencyjnie ustawiamy element na kolejnej pozycji.

• Proces trwa aż do momentu, gdy wszystkie pozycje są obsadzone.

• Każda pełna konfiguracja jest jedną permutacją.

Podsumowanie:

• Dla 6 elementów liczba permutacji jest bardzo duża, dlatego w praktyce często:

  • nie wypisuje się wszystkich permutacji,

  • lub przerywa algorytm po znalezieniu konkretnego rozwiązania.

• Problem ten jest klasycznym przykładem rekurencji i cofania (backtrackingu) oraz doskonałym ćwiczeniem algorytmicznego myślenia.