Jak najít všechny permutace řetězce v Javě

Úvodní myšlenka

Zjištění všech variant uspořádání znaků v daném textovém řetězci je běžným programovacím úkolem. Permutace řetězce představují všechny možné kombinace, které lze vytvořit přeskupením jeho znaků. Například, pokud máme řetězec „abc“, jeho permutacemi budou:

• „abc“
• „acb“
• „bac“
• „bca“
• „cab“
• „cba“

Existuje několik algoritmů, které nám v Javě umožňují nalézt všechny tyto permutace. V tomto článku se podíváme na několik známých přístupů a ukážeme si jejich implementaci pomocí kódu.

Přístupy k výpočtu permutací

1. Rekurzivní metoda řešení

Jednou z nejčastěji používaných technik pro výpočet všech permutací je rekurzivní přístup. Tato metoda spočívá v tom, že se nejprve vygenerují všechny permutace daného řetězce bez jeho prvního znaku. Následně se pro každou z těchto permutací vloží první znak na všechny možné pozice, čímž se vytvoří kompletní sada permutací původního řetězce.

import java.util.ArrayList;
import java.util.List;

public class Permutations {

    public static List<String> ziskejPermutace(String str) {
        if (str.length() == 0) {
            return new ArrayList<>();
        }

        List<String> permutace = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            char prvniZnak = str.charAt(i);
            String zbyvajiciZnaky = str.substring(0, i) + str.substring(i + 1);
            for (String permutaceZbytku : ziskejPermutace(zbyvajiciZnaky)) {
                permutace.add(prvniZnak + permutaceZbytku);
            }
        }

        return permutace;
    }

    public static void main(String[] args) {
        List<String> permutace = ziskejPermutace("abc");
        System.out.println(permutace);
    }
}

2. Iterativní postup

Alternativním způsobem generování permutací je iterativní metoda, která vytváří permutace jednu po druhé. Algoritmus začíná seřazeným původním řetězcem. Následně opakovaně prohazuje sousední znaky, dokud se nedosáhne poslední permutace.

import java.util.ArrayList;
import java.util.List;

public class Permutations {

    public static List<String> ziskejPermutace(String str) {
        List<String> permutace = new ArrayList<>();
        char[] znaky = str.toCharArray();

        int n = znaky.length;
        int[] indexy = new int[n];
        for (int i = 0; i < n; i++) {
            indexy[i] = i;
        }

        do {
            StringBuilder sb = new StringBuilder();
            for (int i : indexy) {
                sb.append(znaky[i]);
            }

            permutace.add(sb.toString());

            int j = n - 2;
            while (j >= 0 && indexy[j] >= indexy[j + 1]) {
                j--;
            }

            if (j >= 0) {
                int k = n - 1;
                while (indexy[j] >= indexy[k]) {
                    k--;
                }

                int docasna = indexy[j];
                indexy[j] = indexy[k];
                indexy[k] = docasna;

                for (int l = j + 1, r = n - 1; l < r; l++, r--) {
                    docasna = indexy[l];
                    indexy[l] = indexy[r];
                    indexy[r] = docasna;
                }
            }

        } while (indexy[0] < n - 1);

        return permutace;
    }

    public static void main(String[] args) {
        List<String> permutace = ziskejPermutace("abc");
        System.out.println(permutace);
    }
}

3. Využití knihovny pro permutace

Pro jednodušší řešení můžete využít knihovnu Apache Commons Lang. Tato knihovna obsahuje třídu Permutator, která umožňuje generovat všechny permutace dané sekvence.

import org.apache.commons.lang3.Permutation;
import java.util.ArrayList;
import java.util.List;

public class Permutations {

    public static void main(String[] args) {
        String str = "abc";
        List<String> permutace = new ArrayList<>();

        Permutation perm = new Permutation(str.toCharArray());
        while (perm.hasNext()) {
            permutace.add(new String(perm.next()));
        }

        System.out.println(permutace);
    }
}

Závěrečné shrnutí

V tomto článku jsme si představili různé přístupy pro vygenerování všech permutací řetězce v Javě. Rekurzivní metoda je intuitivní a snadno implementovatelná, iterativní metoda je efektivnější, zejména pro delší řetězce. Knihovna Apache Commons Lang poskytuje jednoduchý způsob, jak generovat permutace bez nutnosti psát vlastní algoritmus.

Výběr nejlepší metody závisí na konkrétních požadavcích a délce řetězce. Pro menší řetězce může být rekurzivní metoda dobrou volbou, zatímco pro delší řetězce je vhodnější iterativní metoda nebo knihovna pro permutace.

Často kladené otázky

1. Kolik permutací má řetězec o délce n?
Počet permutací řetězce o délce n je n! (n faktoriál).

2. Jaká je typická složitost algoritmu pro generování permutací?
Průměrná složitost je O(n!), kde n je délka řetězce.

3. Co je knihovna Apache Commons Lang?
Knihovna Apache Commons Lang je kolekce užitečných tříd pro obecné účely, které rozšiřují možnosti Javy.

4. Je rekurzivní metoda vhodná pro velké řetězce?
Rekurzivní metoda může vést k vyčerpání paměti při práci s velmi dlouhými řetězci.

5. Která metoda je nejefektivnější pro dlouhé řetězce?
Pro dlouhé řetězce jsou nejefektivnější iterativní metoda nebo knihovna Apache Commons Lang.

6. Lze použít Collections.sort() pro seřazení permutací?
Třída Collections.sort() nemůže seřadit permutace, protože neimplementuje potřebné rozhraní pro porovnávání.

7. Jak mohu převést řetězec na pole znaků?
Metoda String.toCharArray() vrátí pole znaků, které reprezentuje daný řetězec.

8. Mohu použít StringBuilder pro vytvoření permutací?
Ano, třída StringBuilder nabízí efektivní způsob, jak vytvářet a manipulovat s řetězci.