Java实现字符串的全排列

在Java中实现字符串的全排列需要使用递归算法。以下是具体的实现过程：

算法思路

1. 将字符串转换为字符数组。
2. 对字符数组进行排序，确保全排列按照字典序输出。
3. 从第一个字符开始，依次和后面的字符交换位置。
4. 对第一步和第三步进行递归操作，直到选定的第一个字符后面没有其他可选字符为止。
5. 交换字符数组中已经选定的字符和下一位字符的位置，回溯到上一层递归，并继续选择后面的字符进行全排列。

代码实现

public class StringPermutation {
    public static void permutation(char[] str, int index) {
        if (index == str.length - 1) {
            System.out.println(new String(str));
            return;
        }

        for (int i = index; i < str.length; i++) {
            // 交换字符数组中的位置
            char temp = str[index];
            str[index] = str[i];
            str[i] = temp;

            permutation(str, index + 1);

            // 恢复字符数组中的位置
            temp = str[index];
            str[index] = str[i];
            str[i] = temp;
        }
    }

    public static void main(String[] args) {
        String str1 = "abc";
        char[] chars1 = str1.toCharArray();
        Arrays.sort(chars1);
        permutation(chars1, 0);
        System.out.println("-----------------");
        String str2 = "abcdefg";
        char[] chars2 = str2.toCharArray();
        Arrays.sort(chars2);
        permutation(chars2, 0);
    }
}

示例说明

以字符串“abc”为例，按照算法思路的步骤进行递归操作：

• 第一次递归开始：选定a作为第一个字符，剩下的字符为bc，交换ab两个字符，得到bac。
• 第二次递归开始：选定b作为第一个字符，剩下的字符为ac，交换bc两个字符，得到cab。
• 第三次递归开始：选定c作为第一个字符，剩下的字符为ba，交换cb两个字符，得到cba。
• 第四次递归结束，输出最终排列结果abc。

以字符串“abcdefg”为例，按照算法思路的步骤进行递归操作：

• 第一次递归开始：选定a作为第一个字符，剩下的字符为bcdefg，交换ab两个字符，得到bacdefg。
• 第二次递归开始：选定b作为第一个字符，剩下的字符为acdefg，交换bc两个字符，得到cabdefg。
• 第三次递归开始：选定c作为第一个字符，剩下的字符为abdefg，交换cb两个字符，得到cbadefg。
• ... 依次类推。
• 第四次递归结束，输出最终排列结果abcdefg。