Subj : Re: Generating an Index
To   : comp.programming
From : Willem
Date : Fri Sep 09 2005 07:37 am

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

) For 3-bit numbers one possibility would be
) 1 000
) 2 001
) 3 011
) 4 010
) 5 110
) 6 111
) 7 101
) 8 100
)
) My point is now that this defines a *mapping* from the binary number to the
) (arbitrarily chosen) index in the left-hand column.
)
) So this mapping produces a ranking of 3-bit numbers. For instance, the
) numbers 000 and 111 have index 1 and 6 respectively, i.e. they are now "far
) apart" according to this ranking.

Yes, but 000 and 011 are closer than 000 and 010 in the mapping, but
they're farther apart in hamming distance.

) It should be possible to write an algorithm that calculates the "Gray code
) index" of a given binary number. This index could then be written into your
) third column and used to sort by.

Like stated above, with only 100,000 numbers out of 2^255 possibilities,
that is not going to do much good.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.