如何将Java字符无重复排列方法改写为递归实现以支持扩展？

我编写了一个Java 11方法five6789Scramble，用于生成指定长度的无重复字符排列，且排列不能以charSet的首个字符开头。当前该方法仅支持长度1、2、3的排列，但如果继续按现有方式扩展，代码会愈发冗余臃肿。我希望将其改写为递归实现，避免重复编写代码块，最终要支持到长度10；后续还计划将硬编码的charSet改为输入参数。

我的最终目标是逐位构建数字，找出9*9!个无重复数字的十位数中因数最多和最少的数，这也是排列不能以首个字符（对应数字0）开头的原因。

当前代码如下：

import java.util.ArrayList;
import java.util.Arrays;

//Pretend the class wrapper is here

public static ArrayList<ArrayList<Character>> five6789Scramble(byte length) {
        /*Returns all non-repeating permutations of the characters in charSet that don't start with the zero index
        character
         */
        if(length < 0) {
            System.out.println("input length for five6789Scramble must not be negative");
            throw new IndexOutOfBoundsException();
        }
        ArrayList<Character> charSet = new ArrayList<Character>(
                Arrays.asList('a','b','c','d','e','f','g','h','i','j'
                ));
        if(length>charSet.toArray().length) {
            System.out.println("length specified for five6789Scramble is too long");
            throw new IndexOutOfBoundsException();
        }
        ArrayList<ArrayList<Character>> ret = new ArrayList<ArrayList<Character>>();
        for (byte i=1; i<10; i++) {
            if(length > 1) {
                ArrayList<Character> remainingChars = new ArrayList<Character>(charSet);
                remainingChars.remove(i);
                ArrayList<Character> toAddStarter = new ArrayList<Character>();
                toAddStarter.add(charSet.get(i));
                for (byte j=0; j<remainingChars.toArray().length; j++) {
                    if(length > 2) {
                        ArrayList<Character> toAddStarterTwo = new ArrayList<Character>(toAddStarter);
                        toAddStarterTwo.add(remainingChars.get(j));
                        ArrayList<Character> remainingCharsTwo = new ArrayList<Character>(remainingChars);
                        remainingCharsTwo.remove(j);
                        for(byte k=0; k<remainingCharsTwo.toArray().length; k++) {
                            ArrayList<Character> toAdd = new ArrayList<Character>(toAddStarterTwo);
                            toAdd.add(remainingCharsTwo.get(k));
                            ret.add(toAdd);
                        }
                    }
                    else {
                        ArrayList<Character> toAdd = new ArrayList<Character>(toAddStarter);
                        toAdd.add(remainingChars.get(j));
                        ret.add(toAdd);
                    }
                }
            }
            else {
                ArrayList<Character> toAdd = new ArrayList<Character>();
                toAdd.add(charSet.get(i));
                ret.add(toAdd);
            }
        }
        return ret;
    }

请问是否可以将该方法改写为递归实现，避免添加类似if (length > 3)的重复代码块？

当然可以用递归实现，核心思路是分治构建排列：每次选择一个未使用的字符添加到当前排列末尾，直到排列长度达到指定要求。同时提前处理首字符不能为charSet[0]的限制，避免后续无效递归。

改写后的递归实现 #

import java.util.ArrayList;
import java.util.List;

// 类包装省略
public class PermutationGenerator {

    public static List<List<Character>> generateValidPermutations(int targetLength) {
        // 后续可改为输入参数
        List<Character> charSet = List.of('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j');
        
        // 参数校验
        if (targetLength < 0) {
            throw new IllegalArgumentException("目标长度不能为负数");
        }
        if (targetLength > charSet.size()) {
            throw new IllegalArgumentException("目标长度不能超过字符集大小");
        }

        List<List<Character>> result = new ArrayList<>();
        
        // 首字符不能是charSet的第一个元素，从索引1开始遍历
        for (int i = 1; i < charSet.size(); i++) {
            List<Character> initialPerm = new ArrayList<>();
            initialPerm.add(charSet.get(i));
            
            // 剩余字符：复制原集合并移除已选的首字符
            List<Character> remainingChars = new ArrayList<>(charSet);
            remainingChars.remove(i);
            
            // 递归构建剩余长度的排列
            backtrack(initialPerm, remainingChars, targetLength, result);
        }
        
        return result;
    }

    /**
     * 递归回溯方法
     * @param currentPerm 当前已构建的排列
     * @param remainingChars 剩余可选字符
     * @param targetLength 目标排列长度
     * @param result 存储最终结果的集合
     */
    private static void backtrack(List<Character> currentPerm, List<Character> remainingChars, int targetLength, List<List<Character>> result) {
        // 终止条件：当前排列长度达到目标
        if (currentPerm.size() == targetLength) {
            result.add(new ArrayList<>(currentPerm));
            return;
        }

        // 遍历所有剩余字符，逐个尝试添加到当前排列
        for (int i = 0; i < remainingChars.size(); i++) {
            char selected = remainingChars.get(i);
            
            // 选择字符：添加到当前排列
            currentPerm.add(selected);
            
            // 剩余字符：复制并移除已选字符
            List<Character> newRemaining = new ArrayList<>(remainingChars);
            newRemaining.remove(i);
            
            // 递归构建下一位
            backtrack(currentPerm, newRemaining, targetLength, result);
            
            // 回溯：移除刚添加的字符，尝试下一个选项
            currentPerm.remove(currentPerm.size() - 1);
        }
    }
}

关键改进点 #

• 递归回溯逻辑：通过backtrack方法统一处理所有长度的排列构建，无需针对不同长度写重复的嵌套循环
• 参数解耦：原方法的硬编码charSet已改为类内常量，后续可直接修改为方法输入参数（比如新增重载方法）
• 边界处理优化：参数校验更规范，使用IllegalArgumentException替代IndexOutOfBoundsException，语义更清晰
• 扩展性：无需修改核心逻辑，即可支持长度1到10的所有排列生成

后续扩展建议 #

如果要将charSet改为输入参数，只需修改generateValidPermutations方法，添加字符集参数即可：

public static List<List<Character>> generateValidPermutations(List<Character> charSet, int targetLength) {
    // 参数校验新增对charSet的非空检查
    if (charSet == null || charSet.isEmpty()) {
        throw new IllegalArgumentException("字符集不能为空");
    }
    // 其余逻辑不变，替换原有的charSet常量为输入参数
    // ...
}

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