Java字母全排列生成程序输出重复问题求助

你的代码生成重复排列的核心原因是递归逻辑错误——当前的相邻交换+缩短长度的方式并不是生成全排列的正确算法，它会循环生成相同的排列。比如输入"abc"时，你的逻辑会在递归过程中反复交换相邻元素，导致已经输出过的排列被再次打印。

另外，如果输入字符串包含重复字符（比如"aab"），即使算法正确也会产生重复排列，需要额外的去重处理。

1. 无重复字符的正确全排列实现 #

使用回溯法，通过固定每个位置的字符，递归处理剩余字符，确保每个排列只生成一次：

import java.util.Scanner;

public class Combination {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        char[] arr = input.toCharArray();
        
        generatePermutations(arr, 0);
        
        scan.close();
    }

    private static void generatePermutations(char[] arr, int start) {
        // 当start到达数组末尾时，输出当前排列
        if (start == arr.length - 1) {
            System.out.println(new String(arr));
            return;
        }

        // 遍历从start开始的每个字符，将其与start位置交换，递归处理剩余部分
        for (int i = start; i < arr.length; i++) {
            // 交换当前字符到start位置
            swap(arr, start, i);
            // 递归处理start+1之后的字符
            generatePermutations(arr, start + 1);
            // 回溯，恢复交换前的状态
            swap(arr, start, i);
        }
    }

    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2. 支持重复字符的去重全排列实现 #

如果输入可能包含重复字符，需要在交换前判断当前字符是否和之前的字符重复，避免生成重复排列：

import java.util.Scanner;

public class Combination {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        char[] arr = input.toCharArray();
        
        generateUniquePermutations(arr, 0);
        
        scan.close();
    }

    private static void generateUniquePermutations(char[] arr, int start) {
        if (start == arr.length - 1) {
            System.out.println(new String(arr));
            return;
        }

        // 用数组记录已经使用过的字符，避免重复交换
        boolean[] used = new boolean[256]; // 假设输入是ASCII字符
        for (int i = start; i < arr.length; i++) {
            if (used[arr[i]]) {
                continue; // 已经用过该字符，跳过
            }
            used[arr[i]] = true;
            swap(arr, start, i);
            generateUniquePermutations(arr, start + 1);
            swap(arr, start, i);
        }
    }

    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

原代码的getCombinations方法逻辑存在本质缺陷：

• 每次输出当前数组后，仅交换相邻元素并递归缩短长度
• 当长度缩短到1时，交换首尾元素再递归回到原长度

这种方式会导致排列被循环生成，比如输入"abc"时，会在递归过程中多次回到初始状态，重复输出相同的排列。而回溯法通过固定前n个元素，只递归处理剩余部分，每个排列只会被生成一次。

内容的提问来源于stack exchange，提问作者AR A R