问题:字符串abcd怎样获取abcd、acbd、acdb、adbc、adcb、bacd、bcad、bdac、bdca、cabd、cdba、cadb、cbda等,所有排列。
使用回溯法来生成一个字符串的所有排列
import java.util.ArrayList;
import java.util.List;
public class Permutations {
public static void main(String[] args) {
// 目标字符串
String str = "abcd";
// 调用permute方法获取所有排列,并打印结果
List<String> permutations = permute(str);
for (String permutation : permutations) {
System.out.println(permutation);
}
}
/**
* 生成字符串的所有排列。
* @param str 输入的字符串
* @return 包含所有排列的列表
*/
private static List<String> permute(String str) {
List<String> result = new ArrayList<>();
// 如果字符串为空或长度为0,则返回空列表
if (str == null || str.length() == 0) {
return result;
}
// 使用字符数组,并从第一个字符开始进行排列
char[] chars = str.toCharArray();
permuteHelper(chars, 0, result);
return result;
}
/**
* 递归辅助方法,用于生成排列。
* @param chars 字符数组,用于交换字符以生成排列
* @param index 当前处理字符的位置索引
* @param result 存储所有排列结果的列表
*/
private static void permuteHelper(char[] chars, int index, List<String> result) {
// 如果已经处理到最后一个字符,将当前排列加入结果列表
if (index == chars.length - 1) {
result.add(new String(chars));
} else {
// 对于每个未处理的字符,都尝试将其放在当前位置
for (int i = index; i < chars.length; i++) {
// 交换当前字符与待处理字符
swap(chars, index, i);
// 递归处理下一个字符位置
permuteHelper(chars, index + 1, result);
// 回溯:恢复交换前的状态,以便尝试下一个字符
swap(chars, index, i);
}
}
}
/**
* 交换字符数组中的两个元素。
* @param array 字符数组
* @param a 第一个元素的索引
* @param b 第二个元素的索引
*/
private static void swap(char[] array, int a, int b) {
char temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}