Untitled

Finding list of possible substitutions

if node in array

return true

else:

    for child in nodeChildren

        if ((child not in array) && (child == terminalNode))

            return false

        else

        return checkSubstitute(child)

       

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

       

#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

       

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)

       

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

       

find_equivalent(representation, node){

        // representation is a list which is a valid equivalent representation.

        child = list_of_children_of_node;

        Temp = representation[:]

        for each c in child: Temp.insert(child)

 

 

        find_equivalent(representation, next(node,representation))

        N = next(node,Temp)

        Temp.delete(node)

        Li.append(Temp)

        find_equivalent(Temp, N)

        // Here next function takes a list and a node and returns the next element from the list after node.