由递归辅助函数生成

2024-03-28 15:26:43 发布

您现在位置:Python中文网/ 问答频道 /正文

我想从递归函数(下面的代码)中得到结果,但是很难让输出与我想要的匹配。理想情况下,如果我打电话

print(list(n_queens_solutions(4)))

我会看到的

[[1, 3, 0, 2], [2, 0, 3, 1]]

但是函数返回

[[], []]

我不太熟悉Python生成器;我尝试过各种“yield”和“return”的排列,但都没有用。你知道吗

def n_queens_valid(board):
    for q1 in range(len(board)):
        for q2 in range (1, len(board)-q1):
            if board[q1] == board[q1+q2] or board[q1+q2] == board[q1]+q2 or board[q1+q2] == board[q1]-q2:
                return False
    return True

def n_queens_solutions(n):
    board = []
    return n_queens_helper(0, board, n)

def n_queens_helper(n, board, size):
    if len(board) == size:
        print(board)
        yield board
    else:
        for i in range(size):
            board.append(i)
            if n_queens_valid(board):
                yield from n_queens_helper(n+1, board, size)
            board.pop()

print(list(n_queens_solutions(4)))

上面代码中最后一行的打印应该输出:[[1,3,0,2],[2,0,3,1]],但是返回[[],[]。你知道吗


Tags: inboardforsizelenreturnifdef
2条回答

是的,您需要学习有关生成器的教程,以便更全面地了解它们的工作原理。您目前面临的问题是n_queens_solutions只调用helper函数一次,即第一个分支找不到解决方案,并且显示失败时返回的空板。你知道吗

简单地说,把生成器看作是一个带有书签的函数。当您调用生成器时,它将一直执行,直到到达第一个yield;它返回该值,但保留其所有状态信息:所有变量值、它在代码中的位置等。当您再次调用它时,它将从该点重新启动并继续,直到到达下一个yield,并以这种方式继续,直到它从代码末尾脱落密码。你知道吗

生成器最简单的用途是作为迭代器:

for solution in n_queens_helper(...):

您已经以这种方式使用了它(通过在主程序中构建解决方案列表)和重复部分解决方案(使用yield from),但是您需要在控制流上做更多的工作。尝试插入跟踪语句:

def n_queens_helper(n, board, size):
    print("ENTER helper", n, board)
    if len(board) == size:

现在观察执行的进展。你知道吗

让我们用一个简单的例子来说明发生了什么:

def my_func():
  output = [1,2,3]
  print("Output", output)
  yield output
  print("Let's now clear the output")
  output.clear()
  print("Cleared output", output)

result = my_func()
print("Result", result)
print("Result List", list(result))

输出:

Result <generator object my_func at 0x7fd7ccc2a6d0>
Output [1, 2, 3]
Let's now clear the output
Cleared output []
Result List [[]]
  • 当它调用的函数本身(输出的第一行)时,生成器函数中的任何内容实际上都不会执行。你知道吗
  • 当我们从生成器获取所有内容时(通过调用list(result)),我们运行生成器直到它到达函数的末尾,将所有yield结果放入列表中
  • 如我们所见,由于函数中的所有内容现在都已执行,output.clear()方法也已执行。你知道吗
  • result变量的内容与生成器函数末尾的output变量的内容匹配

为了防止这种行为,一个简单的解决方案是返回一个我们正在返回的值的副本,这样我们以后就可以对它进行操作:yield output[:](不过这是一个浅拷贝)

相关问题 更多 >