如何优化1到N最长因数倍数链求解代码？当前仅支持约20个数

我需要找出1到100的最长数字链，要求相邻数字互为因数或倍数，每个数字只能使用一次。自己编写的Python代码仅能在合理时间内处理约20个数，推测耗时主要在列表复制和pop(i)操作，希望优化代码效率。

测试示例：当范围为1-10时，输出为[4, 8, 1, 5, 10, 2, 6, 3, 9]

原代码：

qty = 100
max_length = 0
max = []

def main():
    numbers = list(range(1, qty + 1))
    solve([], numbers, 0)
    print(max)

def check_result(result):
    global qty, max_length, max
    if len(result) > max_length:
        max = result
        max_length = len(result)   

def solve(bufer, left, index):
    if index == qty:
        check_result(bufer)

    for i in range(len(left)):
        left_c = left.copy()
        bufer_c = bufer.copy()
        next = left_c.pop(i)

        if index == 0 or next % bufer_c[index - 1] == 0 or bufer_c[index - 1] % next == 0:
            bufer_c.append(next)
            solve(bufer_c, left_c, index + 1)
        else:
            check_result(bufer_c)

if __name__ == "__main__":
    main()

原代码核心问题分析 #

1. 频繁列表复制：每次递归都复制整个left和bufer列表，内存开销大且复制操作耗时
2. 低效的pop(i)：列表中间位置的pop需要移动后续元素，时间复杂度为O(n)
3. 无剪枝逻辑：未判断当前路径长度+剩余数字数量是否可能超过已找到的最长链，导致大量无效递归
4. 重复计算因数倍数：每次判断相邻数字关系时都实时取模计算，没有复用结果

优化后的代码 #

qty = 100
max_length = 0
max_chain = []

# 预处理每个数字的可连接邻接表（因数/倍数关系）
adj = [[] for _ in range(qty + 1)]
for num in range(1, qty + 1):
    # 添加所有倍数
    multiple = num * 2
    while multiple <= qty:
        adj[num].append(multiple)
        adj[multiple].append(num)
        multiple += num

def check_result(result):
    global max_length, max_chain
    if len(result) > max_length:
        max_chain = result.copy()
        max_length = len(result)   

def solve(current_chain, available):
    # 剪枝：当前长度+剩余数字数 <= 已找到的最长链，直接终止分支
    if len(current_chain) + len(available) <= max_length:
        return
    # 无可用数字时检查结果
    if not available:
        check_result(current_chain)
        return
    
    last_num = current_chain[-1] if current_chain else None
    # 筛选候选数字：第一个数字可选所有，后续选可连接的数字
    candidates = available if last_num is None else [n for n in adj[last_num] if n in available]
    # 优先处理可连接数少的数字，减少分支数量（剪枝优化）
    candidates = sorted(candidates, key=lambda x: len(adj[x]))
    
    for num in candidates:
        # 回溯操作：修改状态
        available.remove(num)
        current_chain.append(num)
        solve(current_chain, available)
        # 撤销状态
        current_chain.pop()
        available.add(num)
    
    # 无候选数字时检查当前链
    check_result(current_chain)

def main():
    numbers = set(range(1, qty + 1))
    # 遍历所有起始数字，避免遗漏更长链
    for start in range(1, qty + 1):
        if max_length == qty:  # 已找到最长可能链，提前终止
            break
        available = numbers.copy()
        available.remove(start)
        solve([start], available)
    print(f"最长数字链：{max_chain}")
    print(f"链长度：{max_length}")

if __name__ == "__main__":
    main()

关键优化点说明 #

1. 预处理邻接表：提前计算每个数字的可连接数字，避免递归时重复取模计算
2. 回溯替代复制：通过修改-撤销状态的方式，避免每次递归复制列表/集合，大幅减少内存开销和复制耗时
3. 集合管理剩余数字：集合的remove/add操作平均时间复杂度为O(1)，比列表的pop(i)高效
4. 剪枝逻辑：提前终止不可能超过当前最长链的分支，减少无效递归
5. 候选排序优化：优先处理可连接数少的数字，快速减少分支数量，提升剪枝效率

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