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.