我有一个有效的示例,可以生成字符串中所有字符的排列组合,如下所示:
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;
}
我正在尝试实现相同的函数,但返回ArrayList,并以int[]作为参数。我以下递归方式完成此操作:
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;
}
当作为参数传递大小为0、1和2的数组时,一切正常。对于大于2的所有其他大小,我得到了正确数量的排列,但它们会重复出现。这是对于大小==3,并传递{1、5、4}的结果:
1 4 5
1 4 5
5 4 1
5 4 1
4 5 1
4 5 1
如果您遇到了以下问题,请给我一些建议。非常感谢!