推导数组元素存储下标：递归生成语言集合改用数组实现的下标计算问题

这里分两种可行思路，都可以避免使用静态变量带来的线程不安全、多次调用相互干扰的问题：

思路1：使用可变索引计数器（最简单的替代方案） #

静态变量的核心问题是全局共享，多次调用方法会互相影响，也不支持并发调用。可以用引用类型的可变计数器替代：

• 可以用AtomicInteger，或者更轻量的长度为1的int数组（数组是引用类型，修改内部值对所有递归调用可见）

修改后的代码示例：

private static final String EPSILON = "";

private static String[] computeLanguage(char[] alphabet, int n) {
    int k = alphabet.length;
    int cardinality = (pow(k, n+1) - 1) / (k - 1);
    String[] language = new String[cardinality];
    language[0] = EPSILON;
    // 用长度为1的数组存索引，初始值为0
    int[] idx = {0};
    return computeLanguage(alphabet, EPSILON, language, idx, 0, n);
}

private static String[] computeLanguage(char[] alphabet, String prefix, String[] language, int[] idx, int i, int n) {
    if (i < n) {
        for (char symbol : alphabet) {
            String w = prefix + symbol;
            language[++idx[0]] = w;
            computeLanguage(alphabet, w, language, idx, i + 1, n);
        }
    }
    return language;
}

// 自己实现整数幂，避免Math.pow的精度问题
private static int pow(int base, int exp) {
    int res = 1;
    for (int i = 0; i < exp; i++) {
        res *= base;
    }
    return res;
}

思路2：数学公式直接推导X的取值（无需额外计数器） #

这种方案完全不需要计数器，通过前缀的位置和当前深度直接计算下标，需要先明确两个前提：

1. 设字母表长度为k = alphabet.length，当前递归深度为i（当前前缀长度等于i，空串深度为0）
2. 对于深度为i的任意前缀，它的每个子节点的子树（包含子节点本身）的总节点数为S(i) = (k^(n - i) - 1) / (k - 1)，这是深度从i+1到n的所有以该子节点为前缀的字符串总数

你需要给递归方法新增一个参数int currentPos，表示当前前缀在数组中的下标：

• 初始调用时，空串的currentPos = 0
• 遍历第j个字母（需要把foreach改为普通for循环，获取下标j）时，X的取值为：currentPos + 1 + j * S(i)

修改后的代码示例：

private static final String EPSILON = "";

private static String[] computeLanguage(char[] alphabet, int n) {
    int k = alphabet.length;
    int cardinality = (pow(k, n+1) - 1) / (k - 1);
    String[] language = new String[cardinality];
    language[0] = EPSILON;
    // 提前预计算每个深度的S值，避免重复计算
    int[] S = new int[n+1];
    for (int i = 0; i <= n; i++) {
        S[i] = (pow(k, n - i) - 1) / (k - 1);
    }
    return computeLanguage(alphabet, EPSILON, language, 0, 0, n, S);
}

private static String[] computeLanguage(char[] alphabet, String prefix, String[] language, int currentPos, int i, int n, int[] S) {
    if (i < n) {
        int k = alphabet.length;
        for (int j = 0; j < k; j++) {
            char symbol = alphabet[j];
            String w = prefix + symbol;
            // 直接计算X的取值
            int X = currentPos + 1 + j * S[i];
            language[X] = w;
            computeLanguage(alphabet, w, language, X, i + 1, n, S);
        }
    }
    return language;
}

private static int pow(int base, int exp) {
    int res = 1;
    for (int i = 0; i < exp; i++) {
        res *= base;
    }
    return res;
}

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