Subj : Re: Generating an Index
To   : comp.programming
From : Arthur J. O'Dwyer
Date : Fri Sep 09 2005 11:21 am


On Fri, 9 Sep 2005, Willem wrote:
>
> Michael wrote:
> ) However, I have an idea I would like to share. It is based on "Gray code".
> )
> ) All n-bit binray numbers may be ordered, such that neighboring elemens have
> ) a distance of 1.
>
> The problem is that he has 255-bit numbers, and only 100,000 of them.
> To find such a mapping is basically the same as solving a Traveling
> Salesman Problem on the numbers (with hamming distance as path lengths).

   Mmm... not quite. If you can solve the TSP, then you can solve Mary's 
problem, yes. But you don't need to solve the TSP to solve Mary's problem.
There are iterative and recursive ways to construct Gray codes in O(n), 
and then you can assign all the indices in O(n lg n) time. (Of course,
O(n) in the OP's case is O(2^255)...!)
   ...Wait, I see what you mean. Michael was suggesting something like 
this, I think (using 3-bit numbers for simplicity):

     Construct the 3-bit Gray code.
        000, 001, 011, 010, 110, 111, 101, 100
     Index each entry according to its order in the code:
        entry 000 gets "1", 010 gets "4", 100 gets "8"...
     Sort on those indices. Two numbers with consecutive indices have a
     Hamming distance of 1, and all duplicates are folded.

Unfortunately, the OP has many orders of magnitude /fewer/ entries than 
there are indices in the 255-bit Gray code. So we have to look at other 
properties of this ordering, like:

     Two numbers with indices k and k+2 have a Hamming distance of 2.
     If we randomly pick three entries with indices i<j<k, we can't say
        anything about the relationships between Hamming distances ij, jk,
        and ik. It might even be that ik < ij.

So if our entries are 000, 011, 110, 100, we'll end up with them in that 
order, instead of the optimal arrangement 000, 100, 110, 011. Also:

     The entry with index "1" and the entry with index "2^255" will have
        a Hamming distance of 1, but a separation of 2^255 entries!

This last problem can be fixed, though, by taking only half of an n+1-bit 
Gray code, so the first entry is 00000 and the last entry is 11111.

   There are certainly major problems with this solution, although the OP 
/might/ still find it acceptable. I agree with your assessment that there 
is no really "good" answer to the problem.

-Arthur

.