Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem: We all know the simple bijection $\phi: \{0,\ldots,2^{n}-1\} \rightarrow \{0,1\}^n$ by just using binary numbers.

However, is there a bijection $\psi: \{0,\ldots,2^{n}-1\} \rightarrow \{0,1\}^n$ such that $|\psi(i+1)-\psi(i)|^2 \leq 2$ for all $i \in \{0,\ldots,2^{n}-2\}$? Namely a bijection where you never change more than $2$ "bits"?

My approach: After thinking a bit I have the idea that you can proove this by sorting all $\{0,1\}^n$ tuples by the amount of ones that occur and then use this to define your bijection, you would just have to show that it cannot be that there are "jumps" in the sorted list of more than 2 changed bits. However, I am also interested in a concrete definition that could be algorithmically implemented and not just a theoretical approach, namely you need to know which bits to change when you increment your number.

Note: $\{0,1\}^n$ means a tuple of length $n$ with entries $0$ or $1$.

share|improve this question
    
What deos $\{0,1\}^n$ mean? for example can you expand $\{0,1\}^2$ or $\{0,1\}^3$ ? –  Arjang Nov 11 '11 at 10:25
    
@Arjang: $\{0,1\}^2 = \{(0,0),(0,1),(1,0),(1,1)\}$ I hope it is more clear now. –  Listing Nov 11 '11 at 10:30
    
Is it always possible to sort $2^n-1$ numbers in binary in a way that no more than 2 digits change in any of the steps' ? –  Arjang Nov 11 '11 at 10:54
1  
To add to the above comment by Listing and the Answers, in gray codes, exactly one bit changes each time, that is, the Hamming distance between $\psi(i)$ and $\psi(i+1)$ is $1$. However there is no solution if exactly two bits must change each time because the set $\{0,1\}^n$ is now partitioned into two cycles: the $n$-tuples of even Hamming weight and the $n$-tuples of odd Hamming weight, and the transition from one cycle to the other requires an odd number of bits to change. –  Dilip Sarwate Nov 12 '11 at 1:12
2  
@Arjang: It is a common notation to write $A^B$ for sets $A,B$ as the set of functions from $B$ to $A$. Furthermore, in modern set theory $n=\{0,\ldots,n-1\}$, so we can identify $A^n$ as the $n$-tuples of elements of $A$. –  Asaf Karagila Nov 29 '11 at 9:03

3 Answers 3

up vote 11 down vote accepted

What you want is a Gray code, which in fact only changes by one bit at a time.

share|improve this answer
    
Thank you :-) This was indeed what I was looking for. –  Listing Nov 11 '11 at 10:44

you are talking about gray code (which has $|\psi(i+1 \mod 2^n)-\psi(i)|^2 = 1$ for $0 \leq i \lt 2^n$)

and there is a construction proof here

for $n=1$ it is trivial: $\{(1),(0)\}$

for $n+1$ you concatenate the code for $n$ (each prefixed with $0$) with its reverse (with each prefixed with $1$)

share|improve this answer

There are many solutions, especially if you allow changing 2 bits rather than one at a time. But indeed Gray code is the simplest solution. Take the binary representation, then for every bit except the first, add to it (modulo 2) the bit to its left (its value before this modification, so work from right to left if doing this sequentially; a computer can do this in parallel by taking the binary number, and taking bitwise XOR with the same number shifted one place to the right).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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