geek_code geek_code - 3 months ago 9
Python Question

Generating gray codes.

I tried generating gray codes in Python. This code works correctly. The issue is that I am initialising the base case (

n=1,[0,1]
) in the
main
function and passing it to
gray_code
function to compute the rest. I want to generate all the gray codes inside the function itself including the base case. How do I do that?

def gray_code(g,n):
k=len(g)
if n<=0:
return

else:
for i in range (k-1,-1,-1):
char='1'+g[i]
g.append(char)
for i in range (k-1,-1,-1):
g[i]='0'+g[i]

gray_code(g,n-1)

def main():
n=int(raw_input())
g=['0','1']
gray_code(g,n-1)
if n>=1:
for i in range (len(g)):
print g[i],

main()


Is the recurrence relation of this algorithm
T(n)=T(n-1)+n
?

Answer
def gray_code(n):
    def gray_code_recurse (g,n):
        k=len(g)
        if n<=0:
            return

        else:
            for i in range (k-1,-1,-1):
                char='1'+g[i]
                g.append(char)
            for i in range (k-1,-1,-1):
                g[i]='0'+g[i]

            gray_code_recurse (g,n-1)

    g=['0','1']
    gray_code_recurse(g,n-1)
    return g

def main():
    n=int(raw_input())
    g = gray_code (n)

    if n>=1:
        for i in range (len(g)):
            print g[i],

main()
Comments