Coding theory - Algorithm：nmdcode函数while循环运行异常排查求助

原代码核心问题 #

• 变量覆盖错误：函数入参n被内部重新赋值为0，属于不必要的变量污染
• 汉明距离校验逻辑错误：仅校验待加入元素与final_list中任意一个元素的汉明距离等于d就加入，无法保证待加入元素与final_list中所有元素都满足距离要求，不满足“两两之间距离为d”的条件
• 重复添加问题：将元素添加操作放在了遍历final_list的循环内部，只要有一个元素满足距离条件就会触发一次添加，同一个候选元素会被重复加入多次，导致final_list长度统计错误
• 最终判断逻辑错误：最后判断的是len(checker)的值，checker是单个长度为n的序列，永远不会等于你要判断的集合大小M，应该判断len(final_list)
• 逻辑边界问题：如果问题要求的是最小汉明距离至少为d（编码理论常规需求），则距离判断条件需要从diff == d改为diff >= d

import itertools as it

def nmdcode(q, n, M, d):
    # 生成所有长度为n的可重复组合
    combinations = list(it.product(q, repeat=n))
    if not combinations:
        return False
    final_list = [combinations[0]]
    
    # 遍历所有候选元素
    for candidate in combinations[1:]:
        # 标记当前候选是否满足和final_list所有元素的距离要求
        is_valid = True
        for elem in final_list:
            # 计算汉明距离
            diff = sum(x != y for x, y in zip(candidate, elem))
            # 若任意一个元素不满足距离要求，直接跳出循环
            if diff < d: # 若要求恰好等于d，这里改为 diff != d
                is_valid = False
                break
        if is_valid:
            final_list.append(candidate)
            # 提前终止：已经达到要求的大小M直接返回，不用遍历完所有组合
            if len(final_list) >= M:
                return True
    # 遍历完所有元素后判断大小
    return len(final_list) >= M

print(nmdcode([1,2,5], 10, 200, 3))

• 目前的实现是暴力枚举所有组合，当n较大时（比如示例里的n=10，3^10=59049个组合）还能运行，n再大的话会严重占用内存和运算资源，建议改用编码理论的构造性算法（比如汉明码、里德所罗门码构造）代替暴力枚举
• 修正代码中已经加入提前终止逻辑，只要final_list的大小达到M就直接返回，不需要遍历完所有候选元素，大幅提升运行效率

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