4
$\begingroup$

I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the strings.

For example, lexicographic order does not satisfy this property because it may be possible to change the order of the string by changing just one bit.

On the other hand, order according to the number of ones is not good either because it only works for linear number of strings.

Is there such an ordering?

Edit: A solution which only works for random strings is also of interest to me.

$\endgroup$
6
$\begingroup$

No. Given any linear ordering of the $n$-bit strings, find a sequence of at most $n+1$ strings going from the first string in the ordering to the last string in the ordering by single-bit changes per step. Some two adjacent strings $x$ and $y$ in this sequence must be at least $2^n/n$ steps apart from each other in the ordering. But then, unless your definition of "far" only allows linearly many strings to be far apart from each other, there must be some $z$ that is far from $x$ and $y$ but between them in the ordering. So changing one bit from $x$ to $y$ reverses the ordering with $z$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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