Generating gray codes.

Question

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 ?

Harwood

Answer 1

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()

Sad

Wow, amazed to see such an elegant code. Thanks. Time complexity is n^2 right? – Harwood

It's just a matter of thinking step by step. Since your main was already doing what you needed, but you wanted it INSIDE your gray_code function, I just turned your main into gray_code function and renamed your original function to gray_code_recurse. Since it wasn't needed anywhere else, I made it local. As for time complexity: the number of 'digits' is proportional to n. The number of 'numbers' is proportional to 2 ^ n. So I would expect time order to be n * (2 ^ n), or equivalently, since it's only order: n * exp (n). But I may be overlooking something, so don't trust me here... – Sad

Instead of this for i in range (len(g)): print g[i], you could have iterated through the object directly, e.g. for elem in g: print(elem). – Amid

Answer 2

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()

Majuscule

Isn't that the Nth gray code is in the bits of (N-1)^((N-1)>>1) ? – Harwood

I coded this which generates codes till specified n only to realise that its inefficient. A bit lengthy. ideone.com/KuVeCw – Harwood

I didn't quite understand the print statement in your code print "{0:0{1}b}".format(gray,n). What's happening here? – Harwood

it prints the binary representation of gray, padded on the left with zeros until it's n digits long – Majuscule

Great. Thanks for solutions and explanations. – Harwood

Answer 3

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()

Meilen

Answer 4

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)))

Suppress

Beautiful and simple, and all set for Python3. This gets my vote. – Roberson

Answer 5

Here's how I did it. state array need to hold some n-bit gray code for some value of n, from which the next gray-code will be generated and state array will contain the generated gray-code, and so on. Although the state is initialized here to be a n-bit '0' code it can be any other n-bit gray code as well.

Time Complexity: O(2^n) For iteratively listing out each 2^n gray codes.

Space Complexity: O(n) For having n-length state and powers array.

def get_bit(line, bit_pos, state, powers):
    k = powers[bit_pos-1]
    if line % (k // 2):
        return str(state[bit_pos-1])
    else:
        bit = 1 - state[bit_pos - 1]
        state[bit_pos - 1] = bit
        if line % k == 0:
            state[bit_pos - 1] = 1 - bit
            bit = 1 - bit
        return str(bit)


def gray_codes(n):
    lines = 1 << n
    state = [0] * n
    powers = [1 << i for i in range(1, n + 1)]
    for line in range(lines):
        gray_code = ''
        for bit_pos in range(n, 0, -1):
            gray_code += get_bit(line, bit_pos, state, powers)
        print(gray_code)


n = int(input())
gray_codes(n)

Quietly

Answer 6

Clearly this horse has been beaten to death already, but I'll add that if you aren't going to use the cool and time-honored n ^ (n >> 1) trick, the recursion can be stated rather more succinctly:

def gc(n):
  if n == 1:
    return ['0', '1']
  r = gc(n - 1)
  return ['0' + e for e in r] + ['1' + e for e in reversed(r)]

... and the iteration, too:

def gc(n):
  r = ['0', '1']
  for i in range(2, n + 1):
    r = ['0' + e for e in r] + ['1' + e for e in reversed(r)]
  return r

Gustave