python - 解析 "ordered"列表并找到相应的和和加数的算法？

Question

很抱歉，如果之前有人问过这个问题，但我已经搜索了几天，但没有找到与我的问题相关的帮助。

我正在尝试研究一种解析列表(类似于预算表)并将索引分配给 parent 或 child 的方法。父项是其子项的总和，子项是该父项的加数(或没有父项的数字)。

例如:[1,2,3,6]，其中 6 是 1、2 和 3 的父级。

或更复杂的示例:[1,2,3,6,1,4,3,8,14,3,2,3,8,1,4,3,8,16,30 ]，

30 是这个列表的“根”，因为 30 = 14 + 16、14 = 6 + 8、6 = 1 + 2 + 3 等。这个列表总是有点顺序的，也就是说 children 会总是一起出现在 parent 面前(当然，当 parent 是另一位 parent 的 child 时除外)。我试图找到最有效的方法来做到这一点，我的 2 个解决方案使用堆栈，但它们并不是 100% 正确，因为上面的 2 个示例失败了。这是两者的伪代码:

解决方案尝试 1

stack = []
for number in list
    if stack.isEmpty()
        stack.push(number)
    elif stack.peek() > number
        stack.push(number)
    else
        copy = stack
        temp = []
        current = number
        while current > 0
            popped = copy.pop()
            temp.push(popped)
            current -= popped
        if current == 0
            while temp
                child = temp.pop()
                child.parent = number
            stack = copy
    stack.push(number)

解决方案尝试 2

stack = []
for number in list
    stack.push(number)

while stack.size() > 1
    child = stack.pop()
    copy = stack
    temp = []
    if child > stack.peek()
        while current > 0 and copy.size() > 0
            popped = copy.pop()
            temp.push(popped)
            current -= popped    
        if current == 0
            while temp
                child = temp.pop()
                child.parent = number

任何想法或想法将不胜感激。我现在正在用头撞墙。

编辑

复杂的示例解决方案[1,2,3,6,1,4,3,8,14,3,2,3,8,1,4,3,8,16,30]

                   30
            /             \
      14                     16
    /      \              /        \
  6          8           8             8
/  |  \   /  |  \     /  |   \     /   |   \
1  2   3  1  4   3   3   2    3   1    4    3

Answer 1

这是一个有趣的问题。这是一个使用列表作为树的递归解决方案(根位于索引 0，子级位于以下索引):

def get_tree(nums, trees=None):
    trees = trees or []
    if not nums:
        return trees[0] if len(trees) == 1 else None
    val, *nums = nums
    for i in range(len(trees)):
        if val == sum(c[0] for c in trees[i:]):
            result = get_tree(nums,  trees[:i] + [[val] + trees[i:]])
            if result:
                return result
    return get_tree(nums, trees + [[val]])

print(get_tree([1, 2, 3, 6]))
print(get_tree([1, 2, 3, 6, 1, 4, 3, 8, 14, 3, 2, 3, 8, 1, 4, 3, 8, 16, 30]))
print(get_tree([1, 2, 3, 7]))
print(get_tree([1, 2, 3]))

# [6, [1], [2], [3]]
# [30, [14, [6, [1], [2], [3]], [8, [1], [4], [3]]], [16, [8, [3], [2], [3]], [8, [1], [4], [3]]]]
# None
# [3, [1], [2]]

get_tree的逻辑如下:

• 您在迭代数字列表时收集树木列表
• 在 nums 中的每个位置，您可以执行以下两项操作之一:
  • 获取树列表末尾的任何树后缀(trees[i:])，并将它们作为子树放在新树下，并以当前编号作为根
  • 将当前数字作为新树添加到堆栈中
• 当到达列表末尾并且堆栈上只有一棵树时，这就是结果

本质上，您会进行后序遍历，并从中生成所有可能的树，并清除沿途总和不匹配的树。对于正整数，这个过程是确定性的，即要么只有一棵有效树，要么没有。对于非正整数，可能存在多个可能的有效树。这个简单的例子是一个仅包含零的列表，其中任何树都是有效的。