Nsryjdtyk

Quite new to tree Data Structures. I am given 2 variables rules and operators. Each of them is a list of strings. For example:

op = ['&',"|","&"]

rules = ['a','b','c','d']

The len(op) has to always equal len(rules)-1 because op always connect rules or another op.

So in the above, a possible tree is:

     "|"

   /      

"&"        "&"

 |        |   

 "a" "b"  "c"  "d"

Another possible one is

         "&"

       /     

     "|"      "d"

   /      

"&"        "c"

 |       

 "a" "b"  

An invalid tree:

"c"

 |   

"|"  "d"

The above tree is not valid because another above an operator cannot be a rule.

Now as the number of rules and operators increase, there are going to be endless combinations of trees. My question is whether it is possible to generate the above trees randomly? Is there an algorithm for this? More specifically, is there a way to randomly create binary trees given you know what the nodes and leafs must be?

Thanks

I can think of this:

1- shuffle your rules: e.g. ['a','b','c','d'] -> ['c','a','b','d'] (or if you can have repeated and "missing" rules just make a random selection such as ['c','d','b','b','d'] with desired length)

2- make each rule in the list a "singleton" tree (i.e. just a leaf), e.g. 'a' -> Tree('a', None, None)

3- pick a random index i in range(len(rules)-1)

4- pick a random operator oper from op (same here, either shuffle op then take elements one by one from the list, or just select a random one independently every time, depending on what you want... )

5- replace the 2 elements at rules[i:i+2] with a new single element Tree(oper, rules[i], rules[i+1])

6- repeat from step 3 until len(rules) == 1

7- you now have a random tree

Here is my crack at a solution. I decided to split the algorithm into two parts. First I generated a random tree structure using the operators. Then I went through and added the terminals to the current leaf nodes.

op = ['&',"|","+"]

terminals = ['a','b','c','d']



shuffle(op)

shuffle(terminals)







class tree:

    def __init__(self, l, r, v):

        self.left = l

        self.right = r

        self.value = v





root = tree(None, None, op[0])

op.pop(0)

def createNonTerminals(root):

    if len(op) == 0:

        return

    choice = randint(0,1)

    if choice == 0: #binary

        root.left = tree(None, None, op[0])

        op.pop(0)

        if len(op) > 0:

            root.right = tree(None, None, op[0])

            op.pop(0)

            createNonTerminals(root.right)

            createNonTerminals(root.left)



        else:

            createNonTerminals(root.left)

    else:

        choice = randint(0, 1)

        if choice == 1:

            root.right = tree(None, None, op[0])

            op.pop(0)

            createNonTerminals(root.right)

        else:

            root.left = tree(None, None, op[0])

            op.pop(0)

            createNonTerminals(root.left)



def addNonTerminals(root):

    if root.left == None:

        root.left = tree(None, None, terminals[0])

        terminals.pop(0)

    else:

        addNonTerminals(root.left)

    if root.right == None:

        root.right = tree(None, None, terminals[0])

        terminals.pop(0)

    else:

        addNonTerminals(root.right)  

Here is some example outputs

['+']

['&', 'd']

['~', 'f']

['a', '-']

['e', '|']

['b', 'c']



['|']

['&', '~']

['+', '-', 'b', 'a']

['d', 'f', 'e', 'c']