Finding list of possible substitutions

Question

Say we have a binary tree as follow: enter image description here

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.

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?

Thanks in advance!!

Kevin · Accepted Answer · 2012-06-14T18:23:00.207

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

Edit: 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)

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

Regarding your code for finding all equivalent arrays, what if we now extend the tree and each node can have multiple children now? — turtlesoup, Jun 11 '12 at 20:49
The easy but brittle answer is, use more for loops. The harder but robust answer is, replace those many for loops with a cartesian product. — Kevin, Jun 12 '12 at 13:10
Hi Kevin, thanks a lot for your explanation! I don't really understand the last piece of code though, where you used the 'Cartesian Product' in recursion. How does it work? Also is there any way to implement it in Java? Thank you!! — turtlesoup, Jun 14 '12 at 17:42
The cartesian product can be thought of as a way to emulate multiple nested `for` loops in a single line. Comparing it to the second-to-last code snippet, you can imagine that `equivalentTuple` is equal to `[child0Equivalent, child1Equivalent, ..., child5Equivalent]`. The `reduce` method within the `for` loop is a way to combine those child equivalents into a single equivalent, which we can then append to the collection of values to return. — Kevin, Jun 14 '12 at 18:50
As for implementing the cartesian product in Java, it has been discussed elsewhere on StackOverflow, so I am sure it is possible: [1](http://stackoverflow.com/questions/714108/cartesian-product-of-arbitrary-sets-in-java) [2](http://stackoverflow.com/questions/1719594/iterative-cartesian-product-in-java) [3](http://stackoverflow.com/questions/6563589/finding-cartesian-product-in-java) [4](http://stackoverflow.com/questions/9591561/java-cartesian-product-of-a-list-of-lists) — Kevin, Jun 14 '12 at 18:50

sukunrt · Answer 2 · 2012-06-11T20:38:18.833

This logic will work fine to generate all equivalent representations, but with some repetitions, which you can check and correct if you want to.(I'll follow some python conventions on where to copy things)

suppose you want all possible representations from [B,C] For each node in this array you can either substitute it for its children or you can leave it intact. So the general idea of the recursion is this:

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.

Above Li is a global array of representations and you need to call the function find_equivalent for each representation as it is added.

Finding list of possible substitutions

2 Answers2