优化生成数字字符序列的递归函数，提升高长度场景性能

需要实现一个生成指定长度数字字符序列的函数，用于安全算法测试。例如：

• 当patternLength为4时，生成["0000","0001",...,"9999"]
• 当patternLength为3时，生成["000","001",...,"999"]

当前递归实现的函数在长度较大时性能骤降，希望通过缓存或动态规划（DP）优化性能。以下是当前递归代码及存在问题的DP尝试代码：

当前递归实现 #

private static List<char> PossibleCharacters = new List<char>()
{
    '0','1','2','3','4','5','6','7','8','9'
};
public static List<string> SequenceGenerator(int patternLength)
{
    List<string> result = new List<string>();
    if (patternLength > 0)
    {
        List<string> prev = SequenceGenerator(patternLength - 1);
        foreach (string entry in prev)
        {
            foreach (char ch in PossibleCharacters)
            {
                result.Add(entry + ch);
            }
        }
    }
    else
    {
        result.Add("");
    }
    return result;
}

存在问题的DP尝试代码 #

// patternLength = 4
string[] result = new string[10000];
string[] cache = new string[10000];
result.Append("");
dp[0] = "0";
int i = 1;
int j = 0;

foreach (string entry in result)
{
    foreach (char ch in PossibleCharacters)
    {
        cache[i] = entry + ch;
        i++;
    }
    result[j + 1] = j.ToString();
    j++;
}
return cache.toList();

你的尝试代码存在数组操作逻辑错误、未定义变量、递推关系混乱等问题。下面提供两种高效的优化实现：

迭代式DP实现 #

避免递归的栈开销，通过迭代逐步构建序列，逻辑清晰且性能稳定：

private static readonly char[] PossibleCharacters = { '0','1','2','3','4','5','6','7','8','9' };

public static List<string> SequenceGenerator(int patternLength)
{
    // 初始状态：长度为0的序列是空字符串
    List<string> current = new List<string> { "" };

    for (int len = 1; len <= patternLength; len++)
    {
        List<string> next = new List<string>();
        // 基于上一轮结果，为每个字符串拼接所有数字字符
        foreach (string s in current)
        {
            foreach (char c in PossibleCharacters)
            {
                next.Add(s + c);
            }
        }
        // 更新当前状态为下一轮结果
        current = next;
    }

    return current;
}

高性能格式化实现 #

当patternLength较大时，直接利用数字格式化生成补零字符串，避免字符串拼接的临时对象开销，性能最优：

public static List<string> SequenceGenerator(int patternLength)
{
    int totalCount = (int)Math.Pow(10, patternLength);
    List<string> result = new List<string>(totalCount);
    // 构造补零格式字符串，如patternLength=4时为"0000"
    string formatString = new string('0', patternLength);

    for (int i = 0; i < totalCount; i++)
    {
        // 将数字格式化为指定长度的补零字符串
        result.Add(i.ToString(formatString));
    }

    return result;
}

优化说明 #

1. 迭代式DP：通过逐步递推构建序列，消除了递归的栈深度限制和重复调用开销，适合对序列构建过程有自定义需求的场景。
2. 格式化实现：直接利用.NET内置的数字格式化功能，内存占用更低、执行速度更快，适合仅需生成标准补零数字序列的场景。

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