Is there an efficient way to sort a list of integers such that each consecutive one has a low number of bits different from the last? I came up with an O(n^2) algorithm to do it but I'm hoping there's a better way.
-
Show this thread
-
Replying to @gsuberland
If you take a number as a vector of n bits, you are solving TSP in n-dimensional space, kinda.
1 reply 0 retweets 1 like -
Replying to @David3141593 @gsuberland
If you use Manhattan distance, I think this is TSP exactly. "low number of different bits" == "low Manhattan distance in n-dimensional space"
1 reply 0 retweets 0 likes -
Replying to @David3141593
Yup, I stumbled across that last night but didn't have time to research it more. Need to look into TSP solvers more later, although it seems like it might be a bit above my level.
1 reply 0 retweets 0 likes -
Replying to @gsuberland @David3141593
There are actually some variants to the high dimensional TSP that have polynomial time solutions, as long as you can make certain assumptions or don't need exhaustive correctness across the whole result set. It also helps that each dimension is a discrete integer in [0,1].
1 reply 0 retweets 0 likes -
Replying to @gsuberland
Do you need a precise solution? Some kinda heuristic solution like a genetic algorithm or simulated annealing might work well.
1 reply 0 retweets 0 likes -
Replying to @David3141593
Heuristic would work. I'm currently looking into heuristic k-dimensional clustering algorithms for that reason. Unfortunately so far it seems k=64 runs into a lot of curse of dimensionality issues, particularly when the cluster count is of a similar magnitude to n.
2 replies 0 retweets 0 likes -
Replying to @gsuberland
I have an idea to reduce dimensionality. Split the number into, say, 4-bit chunks. For each chunk, treat it as if it were a grey-coded integer, and convert it back into a normal binary integer. Now you've divided the number of dimensions by 4, without discarding locality info.
1 reply 0 retweets 0 likes -
Replying to @David3141593
I'm not sure I fully follow. How would the distance function look?
1 reply 0 retweets 0 likes
Just Euclidean distance (or maybe Manhattan, idk)
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.