Sådan finder du alle permutationer af en streng i Java
Permutering af en streng refererer til processen med at arrangere et sæt af tegn fra strengen i en anden rækkefølge. I Java kan du bruge rekursion eller iteration til at finde alle mulige permutationer af en given streng.
Hvad er en permutation?
En permutation af en streng er enhver arrangeret rækkefølge af tegnene i strengen. For eksempel er “abc”, “acb”, “bac”, “bca”, “cab” og “cba” de seks permutationer af strengen “abc”.
Rekursiv tilgang
En rekursiv tilgang involverer at opdele problemet i mindre underproblemer ved at overveje hvert tegn på skift som det første tegn i permutationen. Denne proces fortsætter, indtil alle permutationer er genereret.
Iterativ tilgang
En iterativ tilgang anvender et loop til at generere permutationer én ad gangen. Den starter med den oprindelige streng og anvender swap-operationer for at generere alle mulige arrangementer.
Implementering i Java
Rekursiv implementering:
java
import java.util.ArrayList;
import java.util.List;
public class Permutation {
public static void main(String[] args) {
String str = "abc";
List<String> permutations = permutations(str);
for (String permutation : permutations) {
System.out.println(permutation);
}
}
public static List<String> permutations(String str) {
List<String> permutations = new ArrayList<>();
if (str == null || str.length() == 0) {
permutations.add("");
return permutations;
}
for (int i = 0; i < str.length(); i++) {
char firstChar = str.charAt(i);
String remainingString = str.substring(0, i) + str.substring(i + 1);
List<String> subPermutations = permutations(remainingString);
for (String subPermutation : subPermutations) {
permutations.add(firstChar + subPermutation);
}
}
return permutations;
}
}
Iterativ implementering:
java
import java.util.ArrayList;
import java.util.List;
public class Iteration {
public static void main(String[] args) {
String str = "abc";
List<String> permutations = permutations(str);
for (String permutation : permutations) {
System.out.println(permutation);
}
}
public static List<String> permutations(String str) {
List<String> permutations = new ArrayList<>();
if (str == null || str.length() == 0) {
permutations.add("");
return permutations;
}
int n = str.length();
char[] arr = str.toCharArray();
int[] indices = new int[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
while (true) {
StringBuilder permutation = new StringBuilder();
for (int i = 0; i < n; i++) {
permutation.append(arr[indices[i]]);
}
permutations.add(permutation.toString());
int i = n - 2;
while (i >= 0 && indices[i] >= indices[i + 1]) {
i--;
}
if (i < 0) {
break;
}
int j = n - 1;
while (indices[j] <= indices[i]) {
j--;
}
swap(indices, i, j);
int head = i + 1;
int tail = n - 1;
while (head < tail) {
swap(indices, head, tail);
head++;
tail--;
}
}
return permutations;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Konklusion
Både rekursive og iterative tilgange kan anvendes til at finde alle permutationer af en streng i Java. Valget af tilgang afhænger af præferencer og den specifikke kontekst. Ved store strenge kan den iterative tilgang være mere effektiv på grund af dens mindre hukommelsesforbrug. Ved mindre strenge kan den rekursive tilgang være mere elegant og letforståelig.
Ofte stillede spørgsmål (FAQ’er)
1. Hvad er forskellen mellem en permutation og en kombination?
En permutation tager hensyn til rækkefølgen af elementer, mens en kombination ikke gør det.
2. Hvordan finder jeg alle permutationer af en streng med mere end én forekomst af et tegn?
Du kan bruge en søgning med tilbageføringer eller en algoritme til gruppering og permutationer.
3. Kan jeg finde permutationer parallelt?
Ja, du kan opdele strengen i understrenge og behandle dem parallelt.
4. Hvorfor er rækkefølgen af tegn i en permutation vigtig?
Rækkefølgen af tegn er vigtig, fordi den ændrer betydningen af permutationen.
5. Hvordan kan jeg generere tilfældige permutationer?
Du kan bruge en tilfældig talgenerator til at vælge en rækkefølge af indekser og derefter arrangere tegnene i den rækkefølge.
6. Hvad er kompleksiteten af algoritmen for permutationer?
Kompleksiteten er O(n!), hvor n er antallet af tegn i strengen.
7. Er der en hurtigere måde at finde permutationer på?
Der er nogle algoritmer, såsom Heap-permutationer, der er lidt hurtigere end den iterative og rekursive tilgang.
8. Hvordan kan jeg optimere min kode til permutationer?
Du kan undgå at generere dubletter ved at holde styr på besøgte permutationer og bruge memoisering til at gemme resultater for underproblemer.