7
$\begingroup$

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$.

  • 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$.2011-11-29

3 Answers 3

11

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

  • 0
    Thank you :-) This was indeed what I was looking for.2011-11-11
4

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$)

2

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).