Question

Part A - Palindromic Bitlists Write a function palindrome binary(n) which returns a list of bitlists of length n, where every bitlist is a palindrome. The returned list of bitlists must be in lexicographical order (think about the order of your options). You must use backtracking to solve this problem (i.e. do not use brute force).

Part B - All Paths Write a function all paths(M, u, v) which takes as input an adjacency matrix of a graph, M, and two vertices u, v and returns a list of all paths from u to v in M. A path is a list of vertices. Note that a path cannot use the same vertex twice, but two different paths can use some of the same vertices. The returned list of paths must be in lexicographical order. You must use backtracking to solve this problem (i.e. do not use brute force).

PYTHON CODE

Answer 1

Program code screenshot:

Part A:

Sample output:

Program code to copy:

# Create a function with the name of

# palindrome_binary with argument of n

def palindromes_binary(n):

# store the resul in the rlist

bitlist = []

# divide the given bits from the mid

# and then append the list

position = int(n/2)

# loop to access the element

for i in range(n+2):

    # Compute the first helf of the bit

    # to bitlist in the palindrome

    firsthalf = bin(i)[2:].zfill(position)

    # modulous the given bitlist to check

    # n is even

    if(n % 2 == 0):

    # Reverse the first half to add the second half in the bitlist

      lexicographical = firsthalf + firsthalf[::-1]

      # reverse the list in the lexicographical order

      bitlist.append(lexicographical)

    # otherwise

    else:

       

     # when n is odd, middle can be 0/1 which is 2 possibilities

      # Check the condition when n is odd

      # two cases are avialable

      # case 1 first half and second half mid by zero

      case1 = firsthalf + '0' + firsthalf[::-1]

      # case 2 first half and second half mid by one

      case2 = firsthalf + '1' + firsthalf[::-1]

      # append the case 1 in reverse order

      bitlist.append(case1)

      # append the case 2 in reverse order

      bitlist.append(case2)

     

    # return the bit list

return bitlist

# Display the palindrome list for

# 5 and 9

print(palindromes_binary(5))

print(palindromes_binary(9))

Program code screenshot:

Part B:

Program code to copy:

# Create a function with the name of

# create_all_paths

def create_all_paths(M,u,v,CN,p):

# Check the current node vertices

   if(CN==v):

       #Display the path when reach the end vertex

       print(p,end=" ")

    # for loop check the path is a list of vertices

   for node,pathExist in enumerate(M[CN]):

       # Check the path cannot use the

       # same vertex twice,

       # but two different paths can

       # use some of the same vertices

       if(pathExist == 1 and (node not in p)):

           # append the node at the end of the list

           p.append(node)

           # Use backtracking to solve all paths

           create_all_paths(M,u,v,node,p)

         

           # pop out the path

           p.pop()

          

# create a function with the name of all_paths

# which takes as input an adjacency

# matrix of a graph, M, and two vertices u, v

def all_paths(M,u,v):

# Display the paths

   print("Paths: ",end=" ")

   # call a list of all paths from u to v in M

   create_all_paths(M,u,v,u,[u])

# Define the required variables

# u, v and M

u=0

v=3

# Adjacency matrix of a graph, M,

M=[

   [0,1,1,0],

   [1,0,1,1],

   [1,1,0,1],

   [0,1,1,0]

   ]

# call all_paths function

all_paths(M,u,v)