使用Java语言给定一个字符串,设计一个算法完成对该字符串的一个全排列的输出。比如:字符串 “abc”,输出结果应该是“abc”、“acb”、“bac”、“bca”、“cab” 和 “cba”。 要求:①使用递归思想,编写一个函数 permutationByRecursion,该函数用来生成给定的字符 串的全排列结果。②使用栈数据结构,将①中编写的算法转换成非递归函数,函数名为: permutationByNoRecursion。(利用课堂上讲解的分解 Hanoi 塔的任务方式),该函数所使用的栈 数据结构只能使用自己定义的栈数据结构,不能使用任何语言提供的栈的完整代码
时间: 2023-04-04 20:03:23 浏览: 48
permutationByRecursion函数的实现:
```
public static void permutationByRecursion(String str) {
if (str == null || str.length() == 0) {
return;
}
permutationByRecursion(str.toCharArray(), 0);
}
private static void permutationByRecursion(char[] chars, int index) {
if (index == chars.length - 1) {
System.out.println(new String(chars));
return;
}
for (int i = index; i < chars.length; i++) {
swap(chars, index, i);
permutationByRecursion(chars, index + 1);
swap(chars, index, i);
}
}
private static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
```
permutationByNoRecursion函数的实现:
```
public static void permutationByNoRecursion(String str) {
if (str == null || str.length() == 0) {
return;
}
char[] chars = str.toCharArray();
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int index = 0;
while (!stack.isEmpty()) {
int preIndex = stack.peek();
if (preIndex != -1 && index < chars.length) {
swap(chars, preIndex, index);
}
if (preIndex == chars.length - 2) {
System.out.println(new String(chars));
}
if (index < chars.length - 1) {
stack.push(index);
index++;
stack.push(-1);
} else {
swap(chars, preIndex, chars.length - 1);
stack.pop();
index = preIndex;
}
}
}
private static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
```