python - Python 生成器中的奇怪错误

Question

我有一个行为非常奇怪的 Knuth 算法(“跳舞链接”)的实现。我找到了解决方法，但这就像魔术一样。下面的脚本测试了 N 皇后问题的代码。该错误出现在第一个函数 solve 中。参数limit是用来限制生成解的个数，默认值0表示“生成所有解”。

#Test generalized exact cover for n queens problem 

def solve(Cols,  Rows, SecondaryIDs=set(), limit = 0):
    for soln in solver(Cols, Rows, SecondaryIDs):
        print('solve:', limit, soln)
        yield soln
        limit -= 1
        if limit == 0: return

def solver(Cols, Rows, SecondaryIDs, solution=[]):
    live=[col for col in Cols if col not in SecondaryIDs] 
    if not live:
        yield solution
    else:
        col = min(live, key = lambda col: len(Cols[col]))        
        for row in list(Cols[col]):                                          
            solution.append(row)                                            
            columns = select(Cols, Rows, row)                        
            for soln in solver(Cols, Rows, SecondaryIDs, solution):
                yield soln
            deselect(Cols, Rows, row, columns)
            solution.pop()

def select(Cols, Rows, row):
    columns = []
    for col in Rows[row]:
        for rrow in Cols[col]:
            for ccol in Rows[rrow]:
                if ccol != col:
                    Cols[ccol].remove(rrow)
        columns.append(Cols.pop(col))  
    return columns

def deselect(Cols, Rows, row, columns): 
    for col in reversed(Rows[row]):
        Cols[col] = columns.pop()
        for rrow in Cols[col]:
            for ccol in Rows[rrow]:
                if ccol != col:
                    Cols[ccol].add(rrow)

n = 5

# From Dancing Links paper
solutionCounts = {4:2, 5:10, 6:4, 7:40, 8:92, 9:352, 10:724}

def makeRows(n):
    # There is one row for each cell.    
    rows = dict()
    for rank in range(n):
        for file in range(n):
            rows["R%dF%d"%(rank,file)] = ["R%d"%rank, "F%d"%file, "S%d"%(rank+file), "D%d"%(rank-file)]
    return rows

def makePrimary(n):
    # One primary column for each rank and file
    prim = dict()
    for rank in range(n):
        prim["R%d"%rank] = {"R%dF%d"%(rank,file) for file in range(n)}
    for file in range(n):
        prim["F%d"%file] = {"R%dF%d"%(rank,file) for rank in range(n)}
    return prim

def makeSecondary(n):
    # One secondary column for each diagonal
    second = dict()
    for s in range(2*n-1):
        second["S%d"%s] = {"R%dF%d"%(r, s-r) for r in range(max(0,s-n+1), min(s+1,n))}
    for d in range(-n+1, n):
        second["D%d"%(-d)]={"R%dF%d"%(r, r+d) for r in range(max(0,-d),min(n-d, n))}
    return second

rows = makeRows(n)
primary = makePrimary(n)
secondary = makeSecondary(n)
primary.update(secondary)
secondary = secondary.keys()
#for soln in solve(primary, rows, secondary, 15):
    #print(soln)
solutions = [s for s in solve(primary, rows, secondary)]
try:
    assert len(solutions) == solutionCounts[n]
except AssertionError:
    print("actual %d expected %d"%(len(solutions), solutionCounts[n]))
for soln in solutions:print(soln)

代码设置为生成 5 皇后问题的前 6 个解决方案，并且运行良好。 (看调用

solutions = [s for s in solve(primary, rows, secondary, 6)]

在第 80 行。)实际上有 10 个解决方案，如果我要求 10 个解决方案，我都会得到所有解决方案。如果我离开限制，那么电话就是

solutions = [s for s in solve(primary, rows, secondary)]

主程序打印十个空列表[] 作为解决方案，但是solve 中的代码打印真正的解决方案。如果我将限制设为 15，也会发生同样的事情。

当我将生成器转换为第 80 行中的列表时，问题似乎出现了。如果我将第 78 行和第 79 行的注释掉的行放回去，并注释掉第 80 行之后的所有内容，程序将按我预期的方式运行.但是我不明白这一点；我经常以这种方式列出生成器返回的对象。

另一件更奇怪的事情是，如果我将第 13 行更改为

yield list(solution)

那么第 80 行的代码在所有情况下都可以正常工作。我不记得我最初编写代码时是如何偶然发现这个问题的。我今天正在看它，并将 yield list(solution) 更改为 yield solution 然后错误变得明显。我不明白这一点； solution 已经是一个列表。事实上，我已经尝试添加行

assert solution == list(solution)

就在第 13 行之前，它永远不会引发 AssertionError。

我完全不知所措。我试图制作一个更小的脚本来重现这种行为，但我没能做到。你明白发生了什么吗，你能(更难)向我解释一下吗？

Answer 1

yield solution

问题是您生成了一个列表，您随后可以从中添加和删除项目。当调用者检查列表时，它已经改变了。您需要返回解决方案的卡住副本，以确保保留每个 yield 语句处的结果。这些中的任何一个都可以:

yield list(solution)
yield solution[:]
yield tuple(solution)