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

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

Úvod

Určení všech permutací daného řetězce je běžný úkol v programování. Permutace řetězce jsou všechna možná uspořádání jeho znaků. Například permutace řetězce „abc“ jsou:

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

Existuje několik algoritmů pro nalezení všech permutací řetězce v Javě. V tomto článku prozkoumáme několik populárních metod a poskytneme ukázky kódu pro jejich implementaci.

Metody pro nalezení permutací

1. Rekurzivní metoda

Jedním z nejběžnějších způsobů, jak najít všechny permutace řetězce, je rekurzivní metoda. Tato metoda funguje tak, že nejprve vytvoří všechny permutace řetězce bez jeho prvního znaku. Poté pro každý z těchto řetězců přidá první znak na všechny možné pozice, tím vytvoří všechny permutace původního řetězce.

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

public class Permutations {

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

List<String> permutations = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
char firstChar = str.charAt(i);
String remainingChars = str.substring(0, i) + str.substring(i + 1);
for (String permutation : getPermutations(remainingChars)) {
permutations.add(firstChar + permutation);
}
}

return permutations;
}

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


2. Iterativní metoda

Iterativní metoda pro nalezení permutací řetězce je založena na myšlence generování permutací jedna po druhé. Algoritmus začíná s původním řetězcem v seřazeném pořadí. Poté opakovaně vyměňuje sousední znaky, dokud není dosaženo poslední permutace.

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

public class Permutations {

public static List<String> getPermutations(String str) {
List<String> permutations = new ArrayList<>();
char[] chars = str.toCharArray();

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

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

permutations.add(sb.toString());

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

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

int temp = indices[j];
indices[j] = indices[k];
indices[k] = temp;

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

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

return permutations;
}

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


3. Permutační knihovna

Pro jednoduchý způsob, jak najít všechny permutace řetězce, můžete použít knihovnu Apache Commons Lang. Knihovna obsahuje třídu Permutator, která generuje všechny permutace zadané sekvence.

java
import org.apache.commons.lang3.Permutation;

public class Permutations {

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

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

System.out.println(permutations);
}
}


Závěr

V tomto článku jsme prozkoumali různé metody pro nalezení všech permutací řetězce v Javě. Rekurzivní metoda je jednoduchá a snadno implementovatelná, zatímco iterativní metoda je účinnější, zejména pro dlouhé řetězce. Permutační knihovna Apache Commons Lang poskytuje jednoduchý způsob, jak generovat permutace bez nutnosti implementace vlastního algoritmu.

Volba nejlepší metody závisí na konkrétních požadavcích a velikosti řetězce. Pro malé řetězce je rekurzivní metoda dobrou volbou, zatímco pro větší řetězce je iterativní metoda nebo permutační knihovna vhodnější.

Časté dotazy

1. Kolik permutací má řetězec o délce n?
Existuje n! permutací řetězce o délce n.

2. Jaká je průměrná složitost algoritmu pro nalezení 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 sada utilitních tříd pro obecné účely, které rozšiřují základní funkčnost Javy.

4. Lze použít rekurzivní metodu pro nalezení permutací velkých řetězců?
Rekurzivní metoda může mít nedostatek paměti pro velké řetězce.

5. Jaká je nejúčinnější metoda pro nalezení permutací dlouhých řetězců?
Iterativní metoda nebo permutační knihovna Apache Commons Lang jsou nejefektivnější metody pro nalezení permutací dlouhých řetězců.

6. Mohu použít třídu Collections.sort() pro třídění permutací?
Třída Collections.sort() nemůže třídit permutace, protože neimplementuje potřebné rozhraní pro srovnání.

7. Mohu použít metodu String.toCharArray() pro konverzi řetězce na pole znaků?
Ano, metoda String.toCharArray() vrací pole znaků představující zadaný řetězec.

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