#!/usr/bin/python

def prefix0(s):
	return "0" + s

def prefix1(s):
	return "1" + s

def binary(n):
	# Return a list containing the binary numbers of n digits, in order.

	if n == 0:
		return [""]
	else:
		smaller = binary(n-1)
		left = map(prefix0, smaller)   # a copy of smaller with "0" before each
		right = map(prefix1, smaller)  # a copy of smaller with "1" before each
		return left + right

def gray(n):
	# Return a list containing a complete binary Gray code of n digits.

	if n == 0:
		return [""]
	else:
		smaller = gray(n-1)
		left = map(prefix0, smaller)   # a copy of smaller with "0" before each
		smaller.reverse()              # a reverse-order copy of smaller
		right = map(prefix1, smaller)  # with "1" before each
		return left + right

# You might want to try one of these:

#print "Binary:"
#for i in range(6):
#	print binary(i)

#print "Gray:"
#for i in range(6):
#	print gray(i)