迭代回溯算法问题排查：生成特定子序列时结果缺失

任务需求 #

生成所有长度为2n+1的序列，元素仅为0、-1或1，满足：

• 首元素a₁=0，尾元素a_{2n+1}=0
• 对任意1≤i≤2n，相邻元素差的绝对值|a_{i+1}-a_i|=1或2（即相邻元素不能相等）

问题代码 #

def is_ok(list, k):
    for i in range(1, k + 1):
        if abs(list[i] - list[i-1]) == 0:
            return False
    if k == len(list)-2:
        if abs(list[k+1]-list[k]) == 0:
            return False
    return True

def back_iter(n):
    list_size = n*2+1
    solution = [-1] * list_size
    solution[0] = 0
    solution[2*n] = 0
    position = 1
    while position >= 1:
        if is_ok(solution, position) and position < 2*n-1:
            if position == 2*n-2:
                print(solution)

            position += 1
            solution[position] = -1
        else:
            while solution[position] == 1:
                solution[position] = -1
                position -= 1
            if position < 1:
                break
            solution[position] += 1

输出对比 #

当n=2时，当前输出：

[0, -1, 0, -1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, -1, 0]
[0, 1, 0, -1, 0]

预期输出：

[0, -1, 0, -1, 0]
[0, -1, 0, 1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, 1, 0]
[0, 1, 0, -1, 0]
[0, 1, 0, 1, 0]

问题分析 #

你的迭代回溯算法存在两个核心问题：

1. 打印解的时机错误 #

你在position == 2*n-2时就打印序列，此时仅填充到倒数第三个元素，倒数第二个元素还未完成验证和修改。后续修改倒数第二个元素的值时，不会重新触发打印逻辑，直接漏掉了需要调整倒数第二个元素才能符合条件的解（比如[0,-1,0,1,0]）。

正确的打印时机应该是：当position到达2n-1（即倒数第二个元素的位置），且该元素与最后一个固定为0的元素满足相邻差要求时，再打印完整序列。

2. 验证逻辑冗余且覆盖不全 #

• is_ok函数中循环检查从1到k的所有相邻元素完全冗余：迭代回溯是逐步推进的，每次只需要检查当前position元素和前一个元素的差值即可，无需回溯检查所有历史元素。
• 当position=2n-1时，你的代码逻辑没有触发is_ok验证，导致未检查倒数第二个元素和最后一个元素的差值，既放过了不符合条件的序列（比如[0,1,-1,-1,0]），也没生成符合条件的序列（比如[0,1,-1,1,0]）。

修复建议 #

1. 调整打印逻辑：仅当position到达2n-1且验证通过时，再打印序列。
2. 简化is_ok函数：只检查当前位置与前一位置的差值，以及倒数第二个位置与最后一个位置的差值。

修改后的核心代码示例：

def is_ok(solution, k):
    # 检查当前元素与前一个元素的差值
    if abs(solution[k] - solution[k-1]) == 0:
        return False
    # 若为倒数第二个元素，检查与最后一个元素的差值
    if k == len(solution)-2:
        if abs(solution[k+1] - solution[k]) == 0:
            return False
    return True

def back_iter(n):
    list_size = n*2+1
    solution = [-1] * list_size
    solution[0] = 0
    solution[2*n] = 0
    position = 1
    while position >= 1:
        if is_ok(solution, position):
            if position == 2*n - 1:
                # 验证通过，打印序列（用copy避免后续修改影响输出）
                print(solution.copy())
            elif position < 2*n -1:
                # 继续推进到下一个位置
                position += 1
                solution[position] = -1
        else:
            # 当前值不符合，尝试下一个可能值
            while solution[position] == 1:
                solution[position] = -1
                position -= 1
            if position < 1:
                break
            solution[position] += 1

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