3
$\begingroup$

Gray code is permutation of $\{0,1,2,\dots,2^n-1\}$ such that each of consecutive number is differs only one bit in binary representation.

Example for $n = 3$

$000\\ 001\\ 011\\ 010\\ 110\\ 111\\ 101\\ 100$

Let $s_k$ is bit position of transition $k$ to $k+1$. In example for $n=3$ above are $s_1=3,s_2=2,s_3=3,s_4=1$ and so on

I define adjacent gray code is each consecutive number is differs in adjacent bit. It is, if $s_k=j$ than $s_{k+1}$ is $j-1$ or $j+1$

Example for $n=4$

$0000\\ 0001\\ 0011\\ 0111\\ 0101\\ 0100\\ 0110\\ 0010\\ 1010\\ 1110\\ 1100\\ 1101\\ 1111\\ 1011\\ 1001\\ 1000$

Can anyone design a good algorithm to look for adjacent gray code for $n$ large enough? Maybe it's acceptable for $n\leq10$

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Have you tried constructing such a code explicitly? $\endgroup$ – Yuval Filmus Mar 6 '19 at 15:54
  • 1
    $\begingroup$ WLOG let each Gray code start at all zeroes. Then, for $n = 6$ there does not exist an adjacent Gray code in which the second number is $000001$ or $000010$. Only $000100$ works (and by symmetry $001000$). There does not exist an adjacent Gray code for $n = 7$ at all. $\endgroup$ – orlp Mar 13 '19 at 4:39
  • $\begingroup$ @orlp how to prove for n=6, only 000100 works? $\endgroup$ – L Lawliet Mar 15 '19 at 13:30
  • $\begingroup$ @LLawliet I used a brute force algorithm. $\endgroup$ – orlp Mar 16 '19 at 7:58
  • $\begingroup$ @orlp what kind of BF algo are you using? My BF is just try all permutation and it took very long hours for n = 5 $\endgroup$ – L Lawliet Mar 17 '19 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.