笛卡尔积-使用BackTracking - Python

Question

我正在练习解递归和回溯练习。我遇到了一个问题，要打印列表列表中的所有笛卡尔积，其中每个子列表只包含不同的字符。当然，如果任何一个子列表是空的，那么最终的产品就是一个空列表。

我立刻想到递归地\反向地解决这个问题。我不擅长递归--人们给我的建议是:把递归看作一个黑匣子，只考虑一些合适的基本情况，然后假设你得到了n-1的答案，然后进行递归的步骤。

所以我想，“基本情况是什么？”当列表列表为空时，我将打印一个空列表。如果没有，则返回第一个子列表的第一个字符，加上从下一个子列表对列表列表的递归调用。

def cartesian_product(lst):
    if len(lst)==0:
        return []
    for c in cartesian_product(lst[1:]):
        for s in c:
            return [lst[0][0]] + [s]

我想问题是因为我没有保存当前的子列表，我总是在第一个子列表中。但是，有一个'NoneType‘的错误，我不知道为什么。

我怎么知道什么时候我需要一个函数助手？我什么时候能解决我怎么描述别人告诉我的问题？

Answer 1

首先，虽然这是递归，但我不认为它是回溯，因为我们不会组装，然后可能拒绝，一个候选的解决方案。从概念上讲，我们认为空列表是我们的基本情况，但是Python的循环逻辑不会在空列表中运行。因此，我们使用两个基本情况，一个空参数列表和一个仅包含一个子列表的参数列表。

如果我们的参数只有一个子列表[1, 2, 3]，则结果是[[1], [2], [3]]，否则解决方案是将初始子列表的每个成员附加到(副本的)结果的前面，在其余的子列表上递归地调用我们自己：

def cartesian_product(array):
    product = []

    if array:  # avoid empty base case
        head, *tail = array

        if tail:  # not a base case
            for t in cartesian_product(tail):
                for h in head:
                    product.append([h] + t)
        else:  # one list base case
            product = [[h] for h in head]

    return product

此逻辑还提供了所需的行为，即作为参数子列表中的任何一个出现的空列表会导致返回空列表。