Let say I have 7 integers: 1, 2, 3, 4, 5, 6, 7.
Among the 7 integers, I choose 3 integers. For example, my choice is (1,2,3).
Note1: The order of the integers in the choice doesn't matter. This means that choice (1,2,3) is the same as choice (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).
Note2: You cannot choose an integer more than once. For example, choice (1,1,1) or (1,2,1) is not allowed.
Now, my 2nd choice is (1,2,4).
Let define the distance between two choices is the number of disagreements between them.
For example, distance between choice (1,2,3) and choice (1,2,4) is 1 because we have 1 disagreement (3 and 4).
Let denote d{choice1,choice2} be distance between the 2 choices.
Then, for example,
d{(1,2,3),(1,2,4)}=1
d{(1,2,3),(2,3,1)}=0
d{(1,2,3),(2,5,1)}=1
d{(1,2,3),(7,1,5)}=2
d{(1,2,3),(4,5,6)}=3
Formally speaking, d{choice1,choice2} = 3 - size(Intersection_of(choice1,choice2)).
My question is: How can I encode all possible choices in binary so that the Hamming distance between any 2 encoded binary strings is equal to the the distance (as defined above) between the 2 corresponding choices?
In other words, What is the encoding or mapping function f such that: given x1 and x2 as two choices (for example, (1,2,3) and (1,2,4)), HammingDistance(f(x1),f(x2)) is equal to d{x1,x2} ?
There is no such encoding. The three choices $(1,2,3)$, $(1,2,4)$ and $(1,2,5)$ are all at distance $1$ from each other. But it is impossible to find three bit strings all at Hamming distance $1$ from each other. This is because any two of them must be encoded to strings with weights of opposite parities, i.e. one has an even number of $1$s and the other an odd number of $1$s. Now what would the parity of the third bit string be? :-)
Or IOW, if $x,y,z$ are three bit strings in the Hamming space, then $$ d_H(x,y)+d_H(y,z)\equiv d_H(x,z)\pmod 2, $$ but $1+1\not\equiv1\pmod2.$
It's not all gloom though. The obvious encoding of placing a 1 at position $i$, iff $i$ is part of the set works nicely, if you halve the Hamming distance afterwards. So for example $(1,2,3)\mapsto 1110000$ and $(1,7,5)\mapsto 1000101$. The Hamming distance is four. Halving that gives two, which is what you want.