Python 回溯

Question

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

Answer 1

正如我在评论中建议的那样，您可能希望通过创建 |x[i] - x[i-1]| == m

解决方案的生成器来将计算与 I/O 打印分离

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

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...)")

Python 回溯

Python backtracking

recursive-backtracking