CareerCup

Just do a loop from 0 to 2^n-1 with the following.

unsigned int binaryToGray(unsigned int num)
{
return (num >> 1) ^ num;
}

Gray code.

Here is a code which can achieve this (I think); some optimizations and cleaning are possible.

public String[] return_hamming1_walk(int n) {
     if (n == 1)
	return {"0", "1"};

    String[] smaller_walk = return_hamming1_walk(int n-1);
    String[] walk = new String[2*smaller_walk.length];
    for(int i = 0; i < smaller_walk.length; ++i) {
	walk[i] = "0" + smaller_walk[i];
    }
    for(int i = 0; i < smaller_walk.length; ++i) {
	walk[smaller_walk.length + i] = "1" + smaller_walk[small_walk.length-i-1];
    }
    return walk;
}

How about this.

public static void grayCode(int number) {
        double total = Math.pow(2, number)-1;
        for(int i = 0; i <= total; i++){
            System.out.println(Integer.toBinaryString(toGrayCode(i)));
        }
    }

    public static int toGrayCode(int number){
        return (number >>> 1) ^ number;

}

Here is an iterative version, (also added recursive version just for comparison)
So, that is as optimal as it gets! in space and time

#!/usr/bin/python

#iterative version(binary->gray) (similar logic can be used for gray->binary)
def gray(n,s):
  out=list()
  isrev=False
  while n>=0 and s>1:
    if n<s/2:
     if not isrev:
       out.append('0')
     else:
       out.append('1')
       isrev = not isrev
     s/=2
     
    else: #exact anti-image
      if not isrev:
        out.append('1')
	isrev = not isrev

      else:
        out.append('0')
      s/=2
      n-=s
  print ''.join(out)

#recursive version
def graycode(cur,pos,n,reverse):
  if pos==n:
    print ''.join(cur)
    return

  if not reverse:
    cur[pos]='0'
    graycode(cur,pos+1,n,reverse)

    cur[pos]='1'
    graycode(cur,pos+1,n,not reverse)

  else: #exact anti-image
    cur[pos]='1'
    graycode(cur,pos+1,n,not reverse)

    cur[pos]='0'
    graycode(cur,pos+1,n,reverse)

if __name__=='__main__':
  itr=True

  n=5
  if itr:
    t=1<<n
    for i in range(t):
      gray(i,t)
  else:
    graycode(['0']*n,0,n,False)

private static int next(int n, int i)
	{
		int x = (n >> i) & 0b11;
		switch (x)
		{
		case 0b00: x = 0b01; break;
		case 0b01: x = 0b11; break;
		case 0b11: x = 0b10; break;
		case 0b10: x = 0b00; break;
		}
		n &= ~(0b11 << i);
		n |= x << i;
		return n;
	}
	
	private static int grayCode(int n, int i, int base)
	{
		if (i >= 2)
		{
			for (int j=0; j<4; ++j)
			{
				base = grayCode(n, i - 2, base);
				base = next(base, i - 2);
			}
		}
		else if (i == 0)
		{
			System.out.println(toBinaryString(base, n));
		}
		else
		{
			System.out.println(toBinaryString(base, n));
			System.out.println(toBinaryString(base ^ 1, n));
		}
		return base;
	}

	private static void grayCode(int n)
	{
		grayCode(n, n, 0);
	}

I could have just looked up standard algorithm for Gray codes, but that would have ruined the challenge.

void printAdjacent(int n)
{
	if(n <= 0)
	{
		std::cout << "0" << std::endl;
	}
	else
	{
		std::vector<int> nums = {0, 1};
		int x = 1;

		while(x <= n)
		{
			std::reverse(nums.begin(), nums.end());
			for(int i = nums.size() - 1; i >= 0; i--) nums.push_back(std::pow(10, x) + nums[i]);
			x++;
		}

		for(auto e : nums) 
		{
			std::cout << e << std::endl;
		}
	}
}

My code:

void singlebitchange(int n, int k, int flag, int *p)
{
        int count;
        if(NULL==p)
                return;
        if(k==n)
                {
                        for(count=0;count<n;count++)
                                printf("%d ", p[count]);
                        printf("\n");
                        return;
                }
        p[k]=flag;
        singlebitchange(n, k+1, 0, p);
        p[k]=!flag;
        singlebitchange(n, k+1, 1, p);
}

Recursive solution in python

def tog_main(n):
  for v in tog([0], 1<<(n-1)):
    yield v

def tog(x, bv):
  if bv==0:
    yield x[0]
  else:
    for v in tog(x, bv>>1):
      yield v
    x[0]^=bv
    for v in tog(x, bv>>1):
      yield v

def main():
  for i in tog_main(4):
    print i

vector<int> grayCode(int n) {
vector<int> seq;
seq.push_back(0);
if (n == 0) return seq;
seq.push_back(1);

for (int i = 1; i < n; i++) {
int size = seq.size();
for (int k = size-1; k >= 0; k--) {
seq.push_back(seq[k] | (1 << i));
}
}

return seq;
}

Something very interesting i came across:

wisc-online.com/ Objects/ ViewObject.aspx? ID=IAU8307

interesting read;

introcs.cs.princeton.edu / java/ 23recursion/ GrayCode.java.html

Here is the C# implementation of Gray Code

sealed class Program
    {
        static void Main(string[] args)
        {
            int n = 1000;
            for (uint i = 0; i < n; i++)
            {
                Console.WriteLine(GrayCode(i));
            }
            Console.ReadLine();
        }

        static string GrayCode(uint i)
        {
            uint a = (i >> 1) ^ i;
            return Print(a);
        }

        static string Print(uint i)
        {
            StringBuilder builder = new StringBuilder();
            for (int j = sizeof(uint) * 8 - 1; j >= 0; j--)
            {
                if ((i & (1 << j)) > 0)
                {
                    builder.Append("1");
                }
                else
                {
                    builder.Append("0");
                }
            }
            return builder.ToString();
        }

    }

static void printAllGrayCodes(int n) {

		for (int num = 0; num < 1 << n; num++) {

			int val = 0;
			for (int i = n; i > 0; i--) {
				int x = 0;
				if (i == n) {
					if (num >= Math.pow(2, n - 1))
						x = 1;
				} else {
					int modn = num % (int) Math.pow(2, i + 1);
					if (modn >= Math.pow(2, i - 1)
							&& modn + Math.pow(2, i - 1) < Math.pow(2, i + 1))
						x = 1;
				}
				val |= (x << i - 1);
			}
			System.out.println(val);
		}
	}

#include <iostream>
#include <iomanip>
#include <vector>

void print(std::vector<bool> const & number)
{
   for (int i = number.size(); i > 0; --i) {
      std::cout << (int)number[i-1];
   }
   std::cout << std::endl;
}

void modify(std::vector<bool> & number, std::vector<int> & base, std::vector<int> const & cnt)
{
   for (int i = 0; i < number.size(); ++i) {
      --base[i];
      if (base[i] == 0) {
         number[i] = number[i] ^ 1;
         base[i] = cnt[i];
      }
   }
}

void solve(int n)
{
   std::vector<bool> number(n, false);

   // idx:   3 2 1 0
   // cnt:  16 8 4 2
   // base:  8 4 2 1
   
   std::vector<int> base(n, 0);
   std::vector<int> cnt(n, 0);
   for (int i = 0; i < base.size(); ++i) {
      base[i] = 1 << i;
      cnt[i] = 1 << (i+1);
   }

   long long total = (long long)1 << n;
   // the loop condition can be changed so it breaks out when 0000...0000 appears after 'modify' call, in that case the "n" can be very large
   // now it is limited to number of bits in long long - 1
   for (long long idx = 0; idx < total; ++idx) {
      std::cout << std::setw(3) << idx << ' ';
      print(number);
      modify(number, base, cnt);
   }
}

int main()
{
   int n;
   std::cin >> n;
   solve(n);
   return 0;

public class GrayCode {

static char charArray[] = {'0','0','0','0'};

public static void main(String[] args) {
grayCode(4);
}

static void grayCode(int i){
if (i == 1){
System.out.println(charArray);
charArray[0] = (charArray[0] == '0'?'1':'0');
System.out.println(charArray);
return;
}
grayCode(i-1);
charArray[i-1] = (charArray[i-1] == '0'?'1':'0');
grayCode(i-1);
}
}

void print(int n) {
		int limit = 1 << n;
		for (int i = 0; i < limit; i++) {
			int x = i;
			if(x == 0){
				System.out.print(x);
			}
			while(x > 0){
				System.out.print((x & 1));
				x = x >> 1;
			}
			System.out.println("");
		}

	}

def recursive_solve(n):
    if n == 1:
        yield "0"
        yield "1"
    else:
        sub_result = list(recursive_solve(n - 1))
        for n in sub_result:
            yield "0" + n
        for n in sub_result:
            yield "1" + n[::-1]

n=2: 00, 01, 11, 10
    n=3: 000, 001, 011, 010, 110, 111, 101, 100

It seems like something related to minimunm hamming distance