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

Question

在编书程序中chapter 2.3, there is a function print_part() makes me confused (whole code 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 的调用方式可以像 "doesn't look the same" 一样被调用的原因是方法定义允许可选的第二个参数。如果未明确提供第二个选项，则默认设置为空列表。这就是函数定义中的 partition=[] 所做的。

至于为什么叫"twice"，无非就是在递归的每一步，我们都分支成左右两个分支，然后递归处理左边和右边右侧。

更新（回复你的更新）：

混淆源于这一行，其中 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]]

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

how print_parts() function work in composing program chapter2.3

python

tree

partition-problem