recursive-backtracking - Python回溯

Question

我在 Python 中有一个基本问题，我必须验证我的回溯代码是否找到了一些解决方案（我必须找到 1 到n具有属性的数字的所有子列表|x[i] - x[i-1]| == m）。如何检查是否有解决方案？我的意思是我找到的潜在解决方案，我只是打印它们而不是将它们保存到内存中。如果没有解决方案，我必须打印正确的消息。

Answer 1

正如我在评论中建议的那样，您可能希望通过创建您的解决方案的生成器来将计算与 I/O 打印分离|x[i] - x[i-1]| == m

假设您定义了一个生成器来生成您的解决方案：

def mysolutions(...):
    ....
    # Something with 'yield', or maybe not.
    ....

这是一个生成器装饰器，您可以使用它来检查已实现的生成器是否具有值

from itertools import chain
def checkGen(generator, doubt):
    """Decorator used to check that we have data in the generator."""
    try:
        first = next(generator)
    except StopIteration:
        raise RuntimeError("I had no value!")
    return chain([first], generator)

使用这个装饰器，你现在可以定义你以前的解决方案：

@checkGen
def mysolutions(...):
    ....

然后，您可以简单地使用它来分离您的 I/O：

try:
    for solution in mysolutions(...):
        print(solution) #Probably needs some formatting
except RuntimeError:
    print("I found no value (or there was some error somewhere...)")