Java字符全排列排序问题：生成去重排列并按字符逐个排序

我正在开发一款辅助单词排序游戏的程序，需处理最多7个字符的String ArrayList：先生成所有可能的字符排列（洗牌后去重），再将这些排列按字符逐个进行字母序排序。目前我的代码仅能对单个列表排序，无法生成去重的全排列并实现目标排序，附上现有代码：

import java.util.*;

public class SHUFFLE_SORT_TEST {

    public static  void main(String[] args)
    {           
        ArrayList<String> myList = new ArrayList<String>();
        //Input number of elements in the String array

            System.out.println("How many characters?");

        int characterNumber = new Scanner(System.in).nextInt();
        //get the characters (letters)
            for (int i = 1; i < characterNumber + 1; i++) {
                System.out.println("type in character number: " + i);
                String getChar = new Scanner(System.in).nextLine();



                // add the letters to the String Array one after another

                myList.add(getChar);

                // Printing list before shuffling

                System.out.println("\n\n\nOriginal List : \n" + myList + "\n\n\n");


                /*shuffle (2^n)+1 times (n = number of characters) (2^n+1 is the maximimal number of different possibilities)*/


                //edit: 129 is enough cause max chars == 7 and 2^7+1 = 129

                int n = 129;

                for (int j = 1; j < (n) + 1; j++) {


                    Collections.shuffle(myList);


                    // Printing list after shuffling

                    System.out.println(" \n" + myList + "         " +  j +"\n");

                }          

                //Sort the list

                Collections.sort(myList);      

                System.out.println(" \n" + myList + "         " + "SORTED" +"\n");

            }
    } 
}

当前问题：

• 无法生成去重的全排列（多次洗牌既低效又无法覆盖所有排列，还会产生大量重复）
• 无法将所有排列按字符逐个进行字母序排序

1. 核心思路调整 #

放弃多次洗牌的方式，改用回溯法生成全排列，借助Set自动去重；之后将去重后的排列转换为列表，通过自定义比较器实现逐个字符的字母序排序。

2. 完整代码实现 #

import java.util.*;

public class WordPermutationSorter {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> originalChars = new ArrayList<>();

        // 输入字符数量
        System.out.println("How many characters?");
        int charCount = scanner.nextInt();
        scanner.nextLine(); // 处理输入后的换行符，避免后续读取异常

        // 输入每个字符
        for (int i = 1; i <= charCount; i++) {
            System.out.println("Type in character number: " + i);
            String character = scanner.nextLine().trim();
            originalChars.add(character);
        }

        // 生成去重的全排列
        Set<List<String>> permutationSet = new HashSet<>();
        generatePermutations(originalChars, 0, permutationSet);

        // 转换为列表并按规则排序
        List<List<String>> sortedPermutations = new ArrayList<>(permutationSet);
        sortedPermutations.sort((list1, list2) -> {
            // 从左到右逐个字符进行字母序比较
            for (int i = 0; i < list1.size(); i++) {
                int compareResult = list1.get(i).compareToIgnoreCase(list2.get(i));
                if (compareResult != 0) {
                    return compareResult;
                }
            }
            return 0;
        });

        // 输出结果
        System.out.println("\nOriginal characters: " + originalChars);
        System.out.println("\nAll unique permutations (sorted):");
        for (List<String> perm : sortedPermutations) {
            System.out.println(perm);
        }
    }

    // 回溯法生成全排列
    private static void generatePermutations(List<String> chars, int startIndex, Set<List<String>> resultSet) {
        if (startIndex == chars.size() - 1) {
            // 添加当前排列的副本，避免后续修改影响已存入集合的内容
            resultSet.add(new ArrayList<>(chars));
            return;
        }

        for (int i = startIndex; i < chars.size(); i++) {
            // 交换当前位置与起始位置的字符
            Collections.swap(chars, startIndex, i);
            // 递归生成后续位置的排列
            generatePermutations(chars, startIndex + 1, resultSet);
            // 回溯，恢复原字符顺序
            Collections.swap(chars, startIndex, i);
        }
    }
}

3. 关键改进说明 #

• 去重全排列：用HashSet<List<String>>存储排列，自动过滤重复项；回溯法能高效遍历所有可能的排列，不会遗漏也不会重复。
• 逐个字符排序：自定义Comparator，对两个排列的字符从左到右依次做字母序比较（若需要区分大小写，去掉compareToIgnoreCase即可）。
• 输入优化：统一使用一个Scanner对象，解决原代码中多次创建Scanner导致的输入跳过问题。

内容的提问来源于stack exchange，提问作者lolroflxDhaha