2
$\begingroup$

I am trying to generate a $n$-bit gray code where I can specify two strings $s$ and $t$ that must be consecutive in that gray code. I know that there are ways to generate specific codes (such has the Binary Reflected Gray Code and the Recursive Partition Gray Code), but I need to be able to construct one given any two strings as described above. Is there a way to do this? Or a result that guarantees that this is possible? I am almost certain it is, but haven't been able to find anything.

$\endgroup$
  • $\begingroup$ (I didn't vote to close; this is just general feedback.) 1. This question doesn't seem to have anything to do with trees; it's just a question about binary strings. The tree structure doesn't seem to enter into this anywhere. 2. As such, it's just a question about how to construct a Gray code. Gray codes are well-documented. What have you tried? We expect you to make a serious effort to research the problem on your own, and tell us in the question what you've tried and what approaches you considered and rejected. $\endgroup$ – D.W. Apr 11 '15 at 1:01
  • $\begingroup$ I have edited my question to eliminate the mention of trees. I should have been more careful when describing my question (the application I am working with has to do with this, which is why it was in the question to begin with). $\endgroup$ – user340082710 Apr 11 '15 at 1:09
3
$\begingroup$

Yes. It's always possible, if $s,t$ are at hamming distance one from each other. Let $s,t$ be your two strings at distance one from each other. Then there exists a Gray code sequence where they are adjacent in the Gray code sequence, say $s$ appears right before $t$. Now you immediately obtain a valid solution. Find where $t$ appears in the Gray code sequence, and start going through strings in the Gray code sequence until you get back to $s$. This will have the property you want, as a Gray code sequence is a cyclic sequence where every adjacent pair of strings has hamming distance one.

How do you find that Gray code sequence? There are many possible methods, but here's one easy one. Note that if you have a mapping $f$ on strings that permutes the order of the bits, and you apply $f$ to each element of a Gray code sequence, you obtain another Gray code sequence. The same is true for a mapping $g(x)=x\oplus c$ that xors the input with a constant string $c$. These two facts are enough. Start with any Gray code sequence of your choice; let its first two strings be $a,b$. Let $s,t$ be your two strings that have Hamming distance one. Now you can choose $f,g$ so that $g(f(a))=s$ and $g(f(b))=t$ (namely, choose $f$ to move the bit position where $s,t$ differ to the bit position where $a,b$ differ; and then choose $g(x)=f(a) \oplus s$). This choice of $f,g$ induces a new Gray code sequence: you start with your original Gray code sequence, and apply $f$ to each element of it, then apply $g$ to the result of it. The result is a new Gray code sequence whose first two elements are $s,t$. Thus, if you can iterate through the original Gray code sequence, you now have an easy way to iterate through the new Gray code sequence: you just start iterating at its 3rd element, skipping its first two elements (which will be $s,t$).

The requirement that $s,t$ have Hamming distance one is critical, as otherwise there is a trivial counterexample. Consider 2-bit strings. Suppose the two strings you already have are 00 and 11. Then you want to visit the two strings 01 and 10. However, it doesn't matter what order you visit them in: you won't obtain a solution of the form you want. In particular, there are only two possible sequences (01,10 or 10,01), and neither one has the hamming-distance-one property you wanted.

$\endgroup$
  • $\begingroup$ How is this gray code generated? The two most common examples of gray codes are the binary reflected gray code, and the recursive partition gray code - I need a way to create a gray code such that $s$ and $t$ are beside one another. $\endgroup$ – user340082710 Apr 11 '15 at 1:05
  • $\begingroup$ @ZacharyFrenette, I've revised my answer to explain that part. $\endgroup$ – D.W. Apr 11 '15 at 1:07
  • $\begingroup$ Do these properties have a name? I would like to cite them if possible. $\endgroup$ – user340082710 Apr 11 '15 at 1:13
  • $\begingroup$ @ZacharyFrenette, alas, I don't know. Sorry. $\endgroup$ – D.W. Apr 11 '15 at 1:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.