如何测试求和树？

Question

我有两张清单。一个包含值，另一个包含那些保存在求和树中的级别。（列表长度相同）

例如：

[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_lszip要便宜得多。

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调用。这并不理想。除非您期望获得非常大的值和级别列表，否则可能值得进行vs_ls=list（zip（值，级别）），并以列表方式而不是迭代器方式处理此问题。

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

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

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

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