笛卡尔积 - 使用 BackTracking - Python

Question

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

立马想到解决recursively\backtrackingly。我不擅长递归——人们给我的建议是：将递归视为一个黑盒，只考虑一些适当的基本情况，并归纳假设你得到了 n-1 的答案，并进行递归步骤。

这就是我的想法， "What is the base case?" 当列表列表为空时 - 我将打印一个空列表。如果不是，我 return 第一个子列表的第一个字符，加上从下一个子列表递归调用列表列表。

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

首先，虽然这是递归，但我不认为它是回溯，因为我们不会assemble 然后可能会拒绝候选解决方案。我们在概念上将空列表视为我们的基本情况，但 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

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

笛卡尔积 - 使用 BackTracking - Python

Cartesian product - using BackTracking - Python

python

recursion

backtracking

python-3.x