How to resolve the algorithm List rooted trees step by step in the Ring programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm List rooted trees step by step in the Ring programming language

Table of Contents

Problem Statement

You came back from grocery shopping.   After putting away all the goods, you are left with a pile of plastic bags, which you want to save for later use, so you take one bag and stuff all the others into it, and throw it under the sink.   In doing so, you realize that there are various ways of nesting the bags, with all bags viewed as identical. If we use a matching pair of parentheses to represent a bag, the ways are: For 1 bag, there's one way: for 2 bags, there's one way: for 3 bags, there are two: for 4 bags, four: Note that because all bags are identical, the two 4-bag strings ((())()) and (()(())) represent the same configuration. It's easy to see that each configuration for n bags represents a n-node rooted tree, where a bag is a tree node, and a bag with its content forms a subtree. The outermost bag is the tree root. Number of configurations for given n is given by OEIS A81.

Write a program that, when given n, enumerates all ways of nesting n bags.   You can use the parentheses notation above, or any tree representation that's unambiguous and preferably intuitive. This task asks for enumeration of trees only; for counting solutions without enumeration, that OEIS page lists various formulas, but that's not encouraged by this task, especially if implementing it would significantly increase code size. As an example output, run 5 bags.   There should be 9 ways.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm List rooted trees step by step in the Ring programming language

Source code in the ring programming language

# Project : List rooted trees

list = "()"
addstr = []
flag = 0
newstr = []
str = []
np = [1,2,3,4]
for nr = 1 to len(np)
      if nr = 1
         bg1 = "bag"
       else 
         bg1 = "bags"
      ok
      see "for " + nr + " " + bg1 + " :" + nl
     permutation(list,nr*2)
     listroot(nr*2)
next
see "ok" + nl

func listroot(pn)
        for n = 1 to len(addstr)
             result(addstr[n],pn)
             if flag = 1
                see "" + addstr[n] + nl
                addstr[n]
             ok
        next
 
func result(list,pn)
        flag = 0
        newstr = list
        while substr(newstr, "()") != 0
                 if list = "()" or list = "(())"
                    flag = 1
                    exit
                 ok
                 num = substr(newstr, "()")
                 newstr = substr(newstr, "()", "")
                 if left(list,2) = "()" or right(list,2) = "()" or left(list,4) = "(())" or right(list,4) = "(())"
                    flag = 0
                    exit
                 else 
                    if len(list) != 2 and len(list) != 4 and newstr = ""
                       flag = 1
                       exit
                    ok
                 ok
        end
        
func permutation(list,pn)
       addstr = []
       while true
               str = ""
               for n = 1 to pn
                    rnd = random(1) + 1
                    str = str + list[rnd]
               next
               add(addstr,str)
               for m = 1 to len(addstr)
                    for p = m + 1 to len(addstr) - 1
                         if addstr[m] = addstr[p]
                            del(addstr,p)
                         ok
                    next
               next
               if len(addstr) = pow(2,pn)
                  exit
               ok
       end

  

You may also check:How to resolve the algorithm Tonelli-Shanks algorithm step by step in the Powershell programming language
You may also check:How to resolve the algorithm Simple windowed application step by step in the Perl programming language
You may also check:How to resolve the algorithm Mayan numerals step by step in the Python programming language
You may also check:How to resolve the algorithm Multiplication tables step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Musical scale step by step in the RPL programming language