Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 ?

like image 821
sagar_jeevan Avatar asked Aug 03 '16 08:08

sagar_jeevan


4 Answers

Generating Gray codes is easier than you think. The secret is that the Nth gray code is in the bits of N^(N>>1)

So:

def main():
    n=int(raw_input())
    for i in range(0, 1<<n):
        gray=i^(i>>1)
        print "{0:0{1}b}".format(gray,n),

main()
like image 57
Matt Timmermans Avatar answered Oct 26 '22 20:10

Matt Timmermans


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()
like image 44
Jacques de Hooge Avatar answered Oct 26 '22 21:10

Jacques de Hooge


It's relatively easy to do if you implement the function iteratively (even if it's defined recursively). This will often execute more quickly as it generally requires fewer function calls.

def gray_code(n):
    if n < 1:
        g = []
    else:
        g = ['0', '1']
        n -= 1
        while n > 0:
            k = len(g)
            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]
            n -= 1
    return g

def main():
    n = int(raw_input())
    g = gray_code(n)
    print ' '.join(g)

main()
like image 3
martineau Avatar answered Oct 26 '22 20:10

martineau


What about this:

#! /usr/bin/python3

def hipow(n):
    ''' Return the highest power of 2 within n. '''
    exp = 0
    while 2**exp <= n:
        exp += 1
    return 2**(exp-1)

def code(n):
    ''' Return nth gray code. '''
    if n>0:
        return hipow(n) + code(2*hipow(n) - n - 1)
    return 0

# main:
for n in range(30):
    print(bin(code(n)))
like image 2
Hans Schulz Avatar answered Oct 26 '22 19:10

Hans Schulz