# Untitled

By: a guest on Jul 20th, 2012  |  syntax: None  |  size: 2.42 KB  |  hits: 10  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. Finding list of possible substitutions
2. if node in array
3. return true
4. else:
5.     for child in nodeChildren
6.         if ((child not in array) && (child == terminalNode))
7.             return false
8.         else
9.         return checkSubstitute(child)
10.
11. #returns true if Node n exists in NodeList seq, or if its equivalent exists in seq.
12. function exists(n, seq):
13.     if n in seq:
14.         return True
15.     if not n.hasChildren:
16.         return False
17.     return exists(n.leftChild, seq) and exists(n.rightChild, seq)
18.
19. #gets all possible equivalents for the given node. This includes itself.
20. #An equivalent is a list of nodes, so this method returns a list of lists of nodes.
21. function getPossibleEquivalents(node):
22.     ret = new List()
23.     baseCase = new List()
24.     baseCase.append(node)
25.     ret.append(baseCase)
26.     if not node.hasChildren:
27.         return ret
28.     for each leftEquivalent in getPossibleEquivalents(node.leftChild):
29.         for each rightEquivalent in getPossibleEquivalents(node.rightChild):
30.             ret.append(leftEquivalent + rightEquivalent)
31.     return ret
32.
33. for each child0Equivalent in getPossibleEquivalents(node.child[0]):
34.     for each child1Equivalent in getPossibleEquivalents(node.child[1]):
35.         for each child2Equivalent in getPossibleEquivalents(node.child[2]):
36.             for each child3Equivalent in getPossibleEquivalents(node.child[3]):
37.                 for each child4Equivalent in getPossibleEquivalents(node.child[4]):
38.                     ret.append(child0Equivalent + child1Equivalent + child2Equivalent + child3Equivalent + child4Equivalent + child5Equivalent)
39.
40. from itertools import product
41.
42. def getPossibleEquivalents(node):
43.     ret = [node]
44.     if len(node.children) == 0: return ret
45.     for equivalentTuple in product(map(getPossibleEquivalents, node.children)):
46.         possibleEquivalent = reduce(lambda x,y: x+y, equivalentTuple)
47.         ret.append(possibleEquivalent)
48.     return ret
49.
50. find_equivalent(representation, node){
51.         // representation is a list which is a valid equivalent representation.
52.         child = list_of_children_of_node;
53.         Temp = representation[:]
54.         for each c in child: Temp.insert(child)
55.
56.
57.         find_equivalent(representation, next(node,representation))
58.         N = next(node,Temp)
59.         Temp.delete(node)
60.         Li.append(Temp)
61.         find_equivalent(Temp, N)
62.         // Here next function takes a list and a node and returns the next element from the list after node.