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.
If you use Manhattan distance, I think this is TSP exactly. "low number of different bits" == "low Manhattan distance in n-dimensional space"
-
-
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.
-
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].
- 5 more replies
New conversation -
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.