递归实现十六进制12位特定数字统计功能失效求助

原代码的核心问题 #

• 终止条件返回值错误：当l==12时，返回的是生成器表达式而非布尔值对应的整数，sum无法正确累加有效计数。
• 剩余字符判断逻辑颠倒：all(d[-1]<=h for h in s)的判断逻辑错误，应该检查是否存在比当前最后一个字符小的可选字符，若没有则返回0。
• 初始调用未移除已选字符：调用f(1,d,s)时，未从可选字符集合s中移除已选的初始字符d，逻辑不严谨。
• 奇偶交替判断未正确求值：生成器表达式不会自动执行判断，需要直接使用all(...)获取布尔结果。

修复后的代码 #

from functools import lru_cache

@lru_cache(None)
def f(l, d, s):
    # 终止条件：已选够12位，检查奇偶交替
    if l == 12:
        return 1 if all(int(d[i], 16) % 2 != int(d[i+1], 16) % 2 for i in range(11)) else 0
    
    # 如果剩余字符都不小于当前最后一位，无法继续构建降序序列，返回0
    if all(h >= d[-1] for h in s):
        return 0
    
    # 递归累加所有符合条件的选择：选比当前最后一位小的字符，更新可选集合
    total = 0
    for j in s:
        if j < d[-1]:
            new_s = s.replace(j, "")
            total += f(l + 1, d + j, new_s)
    return total

# 初始调用：第一位选f/e/d/c/b（要凑12位降序，第一位必须足够大，剩余11位需更小）
hex_chars = "0123456789abcdef"
result = sum(f(1, d, hex_chars.replace(d, "")) for d in "fedcb")
print(result)

关键修复点说明 #

• 终止条件修正：将生成器表达式改为直接求值的all(...)，返回1或0作为计数单位，确保sum能正确累加。
• 剩余字符判断修正：改为all(h >= d[-1] for h in s)，准确判断是否无法继续选择更小的字符。
• 初始调用优化：从可选字符中移除已选的初始字符，保证可选集合的正确性。
• 递归逻辑调整：用循环累加替代生成器表达式，逻辑更清晰，便于调试。

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