2

在编写程序第 2.3 章中，有一个函数 print_part() 让我感到困惑（此处为完整代码）：

>>> def print_parts(tree, partition=[]):
        if is_leaf(tree):
            if root(tree):
                print(' + '.join(partition))
        else:
            left, right = branches(tree)
            m = str(root(tree))
            print_parts(left, partition + [m])
            print_parts(right, partition)

>>> print_parts(partition_tree(6, 4))
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

此函数使用最多 4 个到分区 6 的部分打印所有方式。我了解分区算法在 partition_tree() 中的工作原理，并且理解分区树没有问题：

                   4
       _________________________
       |                       |
       4                       3
   _______                    _____
   |     |                    |    |
   ..   ...                ...    ...

但我仍然不知道如何从分区树打印分区方式。特别是这些行：

print(' + '.join(partition))

print_parts(left, partition + [m])
print_parts(right, partition)
# why call twice? and the recursion here didn't looks like the
# way the print_parts() called in the beginning.

更新：

这里的递归看起来不像 print_parts() 一开始调用的方式。

以一个更简单的 args 为例来说明我的困惑：

>>> print_parts(partition_tree(3, 2))
2 + 1
1 + 1 + 1

分区树是：

                         2
           --------------------------------
          2                               1
    ----------------           ------------------------
   F               1           1                     F
               ------        ------------
              T    F         1          F
                           -------
                          T      F

或者

[2, [2, [False], [1, [True], [False]]], [1, [1, [1, [True], [False]],[False]],[False]]]

上面的列表首先作为树的值传递给 func print_parts()。

当去这条线时：

print_parts(left, partition + [m])

左边的值为

[[2, [False], [1, [True], [False]]], [1, [1, [1, [True], [False]],[False]],[False]]]

它不再是一棵树，因为在定义中，树应该具有如下结构：[node, [branch],[branch]]。如果是这样，递归就不能工作。

4

1 回答 1

1

听起来您了解算法，但可能不了解 Python 代码。

print(' + '.join(partition))只是将列表格式化为您看到的输出格式。例如，它将列表[3, 2, 1]转换为字符串'3 + 2 + 1'。

那么print_parts可以以与原始调用“看起来不一样”的方式调用方法的原因是方法定义允许可选的第二个参数。如果没有明确提供第二个选项，则默认设置为空列表。这就是partition=[]函数定义中的作用。

至于为什么叫它“两次”，只是在递归的每一步，我们都分支成两个分支（左右），然后递归处理左侧和右侧。

更新（回复您的更新）：

混淆源于 Python 可以一次分配多个变量的这一行：

left, right = branches(tree)

由于branches(tree)是长度为 2 的列表，因此 2 个元素分别分配给left和right。

所以你说的不是真的：

左边的值为

[[2, [False], [1, [True], [False]]], [1, [1, [1, [True], [False]],[False]],[False]]]

但反而：

left, right = branches(partition_tree(3, 2))
print left
> [2, [False], [1, [True], [False]]]
print right
> [1, [1, [1, [True], [False]], [False]], [False]]
于 2015-04-07T07:12:10.183 回答