Gray Code

We can imagine the binary representations of integer $0$ through $15$ ( $0000,0001,\cdots,1111$ ) as the coordinates of a unit hypercube (of dimension $4$ ).

That way, a Gray code is a Hamiltonian path on this hypercube. Here is a bit of code to compute the total number of paths on the hypercube :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def CountGray(n):
    def Recurse(unused, lastVal, nextSet):
        count = 0
        for changedBit in range(0, min(nextSet + 1, n)):
            newVal = lastVal ^ (1 << changedBit)
            mask = 1 << newVal
            if unused & mask:
                if unused == mask: count += 1
                else: count += Recurse(unused & ~mask, newVal, 
                                               max(nextSet, changedBit + 1))
        return count
    count = Recurse((1 << (1 << n)) - 2, 0, 0)
    for i in range(1, n + 1): count *= 2 * i
    return max(1, count) 
print CountGray(4)

From the wording of the question, it was not obvious what were the permissible starting values for the sequence. My method is is quite similar to Romain Bouchard's in concept and quite different in implementation. $n=4; \\ \text{flip}=\text{Table}\left[2^i,\{i,0,3\}\right]; \\ \text{chain}=\text{list}, \\ \text{Block}[ \\ \{\text{last},\text{bit},\text{test}\}, \\ \text{If}[\text{Length}[\text{list}]=16,\text{Sow}[\text{list}];\text{Return}[]]; \\ \text{last}=\text{Last}[\text{list}]; \\ \text{Do}[ \\ \text{test}=\text{BitXor}[\text{bit},\text{last}]; \\ \text{If}[\neg \text{MemberQ}[\text{list},\text{test}],\text{chain}(\text{Append}[\text{list},\text{test}])];, \\ \{\text{bit},\text{flip}\}]; \\ ] \\ ]; \\ \text{result}=\text{Reap}[\text{chain}(\{0\});]$

This returned a 5712 row 16 column matrix. When 5712 did not work, 16 times that worked.

Fun problem. For the example shown, though, shouldn't 010 be the first element? The hamming distance between 001 and 010 is 2.