We added the one-dimensional ordering problem.
The goal is to arrange `n` objects on a 1-dimensional (e.g., horizontal) axis given a distance matrix describing their location in a potentially high-dimensional or unstructured space.
The objects should be arranged in such a way that, for each object,
- the nearest neighbors on the 1-dimensional axis are also the nearest neighbors in the original space (according to the distance matrix provided),
- the second nearest neighbors on the 1-dimensional axis are also the second nearest neighbors in the original space (according to the distance matrix provided),
- the third nearest neighbors on the 1-dimensional axis are also the third nearest neighbors in the original space (according to the distance matrix provided),
- and so on; with (quadratically) decreasing weights of neighbor distance ranks.
The original distances be limited to integers for the sake of simplicity, but we may use floats as well if we want to.
Either way, we do not care about the actual precise distances (e.g., something like "0.001") between the objects on either the one-dimensional nor the original space.
Only about the distance ranks, i.e., about "2nd nearest neighbor," but not "0.012 distance units away."
The solutions of this problem are thus permutations (orders) of the objects.
Of course, if we really want to plot the objects, such a permutation can easily be translated to `x`-coordinates, say, by dividing the index of an object by the number of objects, which nets values in `[0,1]`.
But basically, we reduce the task to finding permutations of objects that reflect the neighbor structure of the original space as closely as possible.
If such a problem is solved correctly, then the arrangement on the one-dimensional axis should properly reflect the arrangement of the objects in the original space.
Of course, solving this problem exactly may not actually be possible, since an object on a one-dimensional axis may either have exactly two `i`-nearest-neighbors (if it is at least `i` slots away from either end of the permutation) or exactly `1` such neighbor, if it is closer that `i` units.
The object directly at the start of the permutation has only 1 nearest neighbor (the object that comes next).
That next object, however, has two, namely the first object and the third object.
In the original space where the objects come from, however, there may be any number of "nearest neighbors."
Imagine a two-dimensional space where one object sits at the center of a circle of other objects.
Then all other objects are its nearest neighbors, whereas an object on the circle either has exactly two nearest neighbors or, maybe, in the odd situation that the radius equals a multiple of the distance to the neighbors on the circle, three.
Such a structure cannot be represented exactly in one dimension.
But that's OK.
Because we mainly do this for visualization purposes anyway.