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

  • 0
    What deos $\{0,1\}^n$ mean? for example can you expand $\{0,1\}^2$ or $\{0,1\}^3$ ?2011-11-11
  • 0
    @Arjang: $\{0,1\}^2 = \{(0,0),(0,1),(1,0),(1,1)\}$ I hope it is more clear now.2011-11-11
  • 0
    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' ?2011-11-11
  • 0
    In this case yes because all possible tuples are used. The gray code (see the answers) even shows that it is possible with no more than 1 digit to change.2011-11-11
  • 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.2011-11-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$.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).