python - print_parts() 函数在编写程序中的工作原理 chapter2.3

Question

在编书程序中chapter 2.3 ，有一个函数 print_part() 让我感到困惑(整个代码 here ):

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

更新:

recursion here didn't looks like the way the print_parts() called in the beginning.

以一个更简单的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]]。如果是这样，递归将无法工作。

Answer 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。

所以你说的不是真的

the left value is

[[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]]