python - 如何测试求和树？

Question

我有 2 个列表。一个包含值，另一个包含这些值在总和树中保存的级别。 (列表的长度相同)

例如:

[40,20,5,15,10,10] and [0,1,2,2,1,1]

这些列表正确对应，因为

- 40
- - 20
- - - 5
- - - 15
- - 10
- - 10

(20+10+10) == 40 and (5+15) == 20

我需要检查给定的值列表及其级别列表是否正确对应。到目前为止，我已经成功地组合了这个函数，但由于某种原因，它没有为正确的列表数组和数字返回True。此处输入数字将为[40,20,5,15,10,10]，数组将为[0,1 ,2,2,1,1]

def testsum(array, numbers):
    k = len(array)
    target = [0]*k
    subsum = [0]*k
    for x in range(0, k):
        if target[array[x]]!=subsum[array[x]]:
            return False
        target[array[x]]=numbers[x]
        subsum[array[x]]=0
        if array[x]>0:
            subsum[array[x]-1]+=numbers[x]
    for x in range(0, k):
        if(target[x]!=subsum[x]):
            print(x, target[x],subsum[x])
            return False
    return True

Answer 1

我使用 itertools.takewhile 运行它获取每个级别下的子树。将其放入递归函数中并断言所有递归都通过。

我通过获取 next_v 和 next_l 并尽早测试当前节点是否是父节点并且仅构建 稍微改进了我的初始实现子树 如果有东西要构建。这种不等式检查比迭代整个 vs_ls zip 便宜得多。

import itertools

def testtree(values, levels):
    if len(values) == 1:
        # Last element, always true!
        return True
    vs_ls = zip(values, levels)
    test_v, test_l = next(vs_ls)
    next_v, next_l = next(vs_ls)
    if next_l > test_l:
        subtree = [v for v,l in itertools.takewhile(
            lambda v_l: v_l[1] > test_l,
            itertools.chain([(next_v, next_l)], vs_ls))
                   if l == test_l+1]
        if sum(subtree) != test_v and subtree:
            #TODO test if you can remove the "and subtree" check now!
            print("{} != {}".format(subtree, test_v))
            return False
    return testtree(values[1:], levels[1:])

if __name__ == "__main__":
    vs = [40, 20, 15, 5, 10, 10]
    ls = [0, 1, 2, 2, 1, 1]
    assert testtree(vs, ls) == True

不幸的是，它增加了代码的复杂性，因为它提取了我们需要的第一个值，这需要额外的 itertools.chain 调用。这并不理想。除非您希望获得非常大的 values 和 levels 列表，否则可能值得执行 vs_ls = list(zip(values,levels)) 并按列表方式而不是按迭代器方式处理此问题。例如...

...
vs_ls = list(zip(values, levels))
test_v, test_l = vs_ls[0]
next_v, next_l = vs_ls[1]
...

    subtree = [v for v,l in itertools.takewhile(
        lambda v_l: v_l[1] > test_l,
        vs_ls[1:]) if l == test_l+1]

我仍然认为最快的方法可能是使用几乎像状态机的方法迭代一次并获取所有可能的子树，然后单独检查它们。像这样的东西:

from collections import namedtuple

Tree = namedtuple("Tree", ["level_num", "parent", "children"])
# equivalent to
# # class Tree:
# #     def __init__(self, level_num: int,
# #                        parent: int,
# #                        children: list):
# #         self.level_num = level_num
# #         self.parent = parent
# #         self.children = children

def build_trees(values, levels):
    trees = []  # list of Trees
    pending_trees = []
    vs_ls = zip(values, levels)
    last_v, last_l = next(vs_ls)
    test_l = last_l + 1
    for v, l in zip(values, levels):
        if l > last_l:
            # we've found a new tree
            if l != last_l + 1:
                # What do you do if you get levels like [0, 1, 3]??
                raise ValueError("Improper leveling: {}".format(levels))
            test_l = l

            # Stash the old tree and start a new one.
            pending_trees.append(cur_tree)
            cur_tree = Tree(level_num=last_l, parent=last_v, children=[])

        elif l < test_l:
            # tree is finished

            # Store the finished tree and grab the last one we stashed.
            trees.append(cur_tree)
            try:
                cur_tree = pending_trees.pop()
            except IndexError:
                # No trees pending?? That's weird....
                # I can't think of any case that this should happen, so maybe
                # we should be raising ValueError here, but I'm not sure either
                cur_tree = Tree(level_num=-1, parent=-1, children=[])

        elif l == test_l:
            # This is a child value in our current tree
            cur_tree.children.append(v)
    # Close the pending trees
    trees.extend(pending_trees)
    return trees

这应该为您提供一个 Tree 对象列表，每个对象都具有以下属性

level_num  := level number of parent (as found in levels)
parent     := number representing the expected sum of the tree
children   := list containing all the children in that level

完成此操作后，您应该能够简单地检查

all([sum(t.children) == t.parent for t in trees])

但请注意，我无法测试第二种方法。