寻找可能的替代名单 [英] Finding list of possible substitutions

问题描述

说我们有一个二叉树如下：

Say we have a binary tree as follow:

我在寻找一种算法找出A的所有等价我因为包含在这棵树元素的数组。该规则是，如果在一个阵列存在一个节点的所有子，它是等效于具有阵列中的节点。 例如，如果我们有B和C的阵列中，它相当于具有A.所以上面的阵列，F + G = C和C + B = A，所以〔B，F，G]中也相当于A.同样[DEFG]也相当于一个。

I'm looking for an algorithm to find all the equivalence of A. I'm given an array that contains elements in this tree. The rule is, if all the children of a node exist in an array, it is equivalent to having the node in the array. For example, if we have B and C in the array, it is equivalent to having an A. So in the array above, F+G=C, and C+B = A, so [B,F,G] is also equivalent to A. Likewise [D E F G] is also equivalent to A.

我可以递归调用类似checkSubstitute（节点）：

I can recursively call something like checkSubstitute(node):

if node in array
return true
else:
    for child in nodeChildren
        if ((child not in array) && (child == terminalNode))
            return false
        else
        return checkSubstitute(child)

这是否逻辑是否合理？此外，我怎么能存储使用类似上面的算法都相当于阵列？

Does this logic make sense? Also how can I store all the equivalent arrays using an algorithm like the one above?

在此先感谢！

推荐答案

你给不正常工作，因为你永远是第一次迭代循环过程中返回一个值的方法。 假设你有一个数组[D]。然后checkSubstitute（B）返回true，当它应该返回False。

The method you gave doesn't work properly, since you always return a value during the first iteration of the for loop. Suppose you have an array [D]. Then checkSubstitute(B) returns True, when it should return False.

，它更容易只是为了让两个孩子两个显式调用。这是假定每个节点都有零个或两个孩子。如果一个节点可以有一个孩子，其他一些空的检查是必要的。

Instead of using a for loop, it's easier just to make two explicit calls on both of the children. This assumes every node has either zero or two children. If a node can have one child, some additional null checking is necessary.

#returns true if Node n exists in NodeList seq, or if its equivalent exists in seq.
function exists(n, seq):
    if n in seq:
        return True
    if not n.hasChildren:
        return False
    return exists(n.leftChild, seq) and exists(n.rightChild, seq)

让所有等同阵列只是需要一些组合数学。

getting all equivalent arrays just requires a bit of combinatorics.

#gets all possible equivalents for the given node. This includes itself.
#An equivalent is a list of nodes, so this method returns a list of lists of nodes.
function getPossibleEquivalents(node):
    ret = new List()
    baseCase = new List()
    baseCase.append(node)
    ret.append(baseCase)
    if not node.hasChildren:
        return ret  
    for each leftEquivalent in getPossibleEquivalents(node.leftChild):
        for each rightEquivalent in getPossibleEquivalents(node.rightChild):
            ret.append(leftEquivalent + rightEquivalent)
    return ret

编辑： 您可以扩展getPossibleEquivalents的树木恰好为0或N的孩子，通过嵌套N代表循环：

You can extend getPossibleEquivalents for trees with exactly 0 or N children, by nesting N for loops:

for each child0Equivalent in getPossibleEquivalents(node.child[0]):
    for each child1Equivalent in getPossibleEquivalents(node.child[1]):
        for each child2Equivalent in getPossibleEquivalents(node.child[2]):
            for each child3Equivalent in getPossibleEquivalents(node.child[3]):
                for each child4Equivalent in getPossibleEquivalents(node.child[4]):
                    ret.append(child0Equivalent + child1Equivalent + child2Equivalent + child3Equivalent + child4Equivalent + child5Equivalent)

如果你想编写一个函数，可以处理任意数量的子树，你需要采取的每个可能每个孩子的等价的笛卡尔乘积。有些语言实现笛卡尔乘积为你了。例如，在Python：

If you want to write a single function that can handle trees with any number of children, you need to take the Cartesian Product of each possible equivalent of each child. Some languages implement cartesian product for you already. For example, in python:

from itertools import product

def getPossibleEquivalents(node):
    ret = [node]
    if len(node.children) == 0: return ret
    for equivalentTuple in product(map(getPossibleEquivalents, node.children)):
        possibleEquivalent = reduce(lambda x,y: x+y, equivalentTuple)
        ret.append(possibleEquivalent)
    return ret

这篇关于寻找可能的替代名单的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！