Algorytm permutacji dla tablicy liczb całkowitych w Javie
Mam działający przykład generowania wszystkich permutacji znaków w łańcuchu, jak poniżej:
static ArrayList<String> permutations(String s) {
if (s == null) {
return null;
}
ArrayList<String> resultList = new ArrayList<String>();
if (s.length() < 2) {
resultList.add(s);
return resultList;
}
int length = s.length();
char currentChar;
for (int i = 0; i < length; i++) {
currentChar = s.charAt(i);
String subString = s.substring(0, i) + s.substring(i + 1);
ArrayList<String> subPermutations = permutations(subString);
for (String item : subPermutations) {
resultList.add(currentChar + item);
}
}
return resultList;
}
Usiłuję zaimplementować tę samą funkcję, ale zwrócić ArrayList i uzyskać int [] jako parametr. Robię to rekurencyjnie jak poniżej:
static ArrayList<int[]> permutations(int[] arr) {
ArrayList<int[]> resultList = new ArrayList<int[]>();
if (arr.length < 2) {
resultList.add(arr);
return resultList;
}
for (int i = 0; i < arr.length; i++) {
int currentItem = arr[i];
int[] newArr = new int[arr.length - 1];
int[] newPermutation = new int[arr.length];
int j;
// System.arraycopy(arr, 0, newArr, 0, i);
// System.arraycopy(arr, i + 1, newArr, i, arr.length - i - 1);
for (j = 0; j < i; j++) {
newArr[j] = arr[j];
}
for (j = i + 1; j < arr.length; j++) {
newArr[j - 1] = arr[j];
}
ArrayList<int[]> subPermutations = permutations(newArr);
newPermutation[0] = currentItem;
// for (int i1 = 0; i1 < subPermutations.size(); i1++) {
// for (j = 0; j < subPermutations.get(i1).length; j++) {
// newPermutation[j + 1] = subPermutations.get(i1)[j];
// }
//
// resultList.add(newPermutation);
// }
for (int[] item : subPermutations) {
for (j = 0; j < item.length; j++) {
newPermutation[j + 1] = item[j];
}
resultList.add(newPermutation);
}
// return resultList;
}
return resultList;
}
Podczas przekazywania tablic o rozmiarze 0, 1 i 2 jako parametru wszystko jest w porządku. Dla wszystkiego innego niż 2 otrzymuję prawidłową liczbę permutacji, ale się powtarzają. Oto wynik dla rozmiaru == 3 i przejścia {1, 5, 4}:
1 4 5
1 4 5
5 4 1
5 4 1
4 5 1
4 5 1
Proszę dać mi kilka rad, jeśli wcześniej napotkałeś te problemy.
Z góry dziękuję!