Съдържание
Как да намерите всички пермутации на низ в Java
Пермутацията на низ е подредена последователност от неговите елементи. Например, пермутациите на низа „abc“ са:
– abc
– acb
– bac
– bca
– cab
– cba
Пермутациите се използват в различни приложения, като криптография, комбинаторика и генериране на тестови данни.
В Java има няколко начина за генериране на всички пермутации на низ. В тази статия ще разгледаме два от най-често използваните метода:
рекурсия
Рекурсивният подход включва разделяне на проблема на по-малки подпроблеми и използване на решението на подпроблемите за намиране на решението на оригиналния проблем.
Ето рекурсивна функция, която генерира всички пермутации на низ:
java
public static List<String> permute(String str) {
if (str.length() == 1) {
return Arrays.asList(str);
}
List<String> permutations = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
String remaining = str.substring(0, i) + str.substring(i + 1);
List<String> subPermutations = permute(remaining);
for (String subPermutation : subPermutations) {
permutations.add(ch + subPermutation);
}
}
return permutations;
}
Итерация
Итеративният подход включва използването на цикли за генериране на всички пермутации на низ.
Ето итеративна функция, която генерира всички пермутации на низ:
java
public static List<String> permute(String str) {
List<String> permutations = new ArrayList<>();
int[] index = new int[str.length()];
for (int i = 0; i < index.length; i++) {
index[i] = i;
}
do {
StringBuilder permutation = new StringBuilder();
for (int i : index) {
permutation.append(str.charAt(i));
}
permutations.add(permutation.toString());
int j = index.length - 2;
while (j >= 0 && index[j] >= index[j + 1]) {
j--;
}
if (j >= 0) {
int k = index.length - 1;
while (index[k] <= index[j]) {
k--;
}
swap(index, j, k);
}
reverse(index, j + 1);
} while (nextPermutation(index));
return permutations;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void reverse(int[] arr, int start) {
int end = arr.length - 1;
while (start < end) {
swap(arr, start, end);
start++;
end--;
}
}
private static boolean nextPermutation(int[] arr) {
int i = arr.length - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) {
i--;
}
if (i >= 0) {
int j = arr.length - 1;
while (arr[j] <= arr[i]) {
j--;
}
swap(arr, i, j);
reverse(arr, i + 1);
return true;
}
return false;
}
Кой метод да използвате?
Рекурсивният подход е по-прост за разбиране, но може да има проблеми със стека, ако низът е твърде дълъг. Итеративният подход е по-ефективен по отношение на паметта, но е по-сложен за разбиране.
Заключение
Генерирането на всички пермутации на низ може да бъде решаващ проблем в различни приложения. В Java има няколко метода за генериране на пермутации, като рекурсия и итерация. Изборът на метода зависи от дължината на низа и изискванията за ефективност на приложението.
Често задавани въпроси
1. Колко пермутации има наниз с дължина n ?
Броят на пермутациите на низ с дължина n е n!.
2. Как да генерирам пермутациите на низ, без да използвам рекурсия или итерация ?
Можете да използвате библиотеката Apache Commons Lang, която предоставя метода permutation().
3. Как да намеря к-та пермутация наниз ?
Можете да използвате алгоритъма на Джонсън-Туки, за да намерите к-та пермутация на низ.
4. Как да разбера дали два низа са пермутации един на друг ?
Можете да сортирате и двата низа и да проверите дали са равни.
5. Как да генерирам всички циклични пермутации на низ ?
Цикличната пермутация на низ е пермутация, при която последният елемент се поставя в началото. Можете да генерирате всички циклични пермутации на низ, като започнете с произволна пермутация и след това ротирате низа с един елемент наляво.
6. Как да генерирам всички пермутации на низ, който съдържа дубликати ?
Можете да използвате алгоритъма на Heap, за да генерирате всички пермутации на низ, който съдържа дубликати.
7. Как да генерирам всички уникални пермутации на низ ?
Можете да използвате Java колекцията Set, за да съхранявате уникални пермутации.
8. Как да генерирам всички пермутации на низ, който съдържа ограничения ?
Можете да използвате ограниченията, за да намалите броя на пермутациите, които се генерират. Например, ако има ограничение, че два елемента не могат да бъдат разменени, тогава можете да премахнете пермутациите, които нарушават това ограничение.