Algorithm for ordering data so that neighbor elements are as identical as possible

Unfortunately, this problem is NP-complete. You can show this by a reduction from the Hamiltonian path problem on planar 3-regular bipartite graphs, which is also NP-complete.

As an overview of the proof: we will create a 3-Tuple for each vertex of our graph, such that pairs of corresponding 3-Tuples have dissimilarity equal to 2 if the vertices are adjacent, and dissimilarity equal to 3 if the vertices are not adjacent. The members of each vertex’s 3-Tuples will correspond uniquely to the vertex’s incident edges.

Proof:
Suppose we’re given as input an undirected planar cubic bipartite graph G = (V, E) on which we’re trying to find a Hamiltonian path. We can find a 3-coloring of the edges in linear time. Suppose our three edge-colors are 0, 1, 2. For each edge e in E, give it a unique natural number label L(e) such that L(e) mod 3 is equal to e‘s color.

For example, with this cubic planar bipartite graph:

We can color the edges with colors 0, 1 and 2:

And then label the edges with minimal natural numbers L(e) that respect the colors mod 3:

For each vertex v in V, create a 3-Tuple T = (t0, t1, t2), where t0, t1, t2 are the labels of edges incident to v with remainders equal to 0, 1, 2 respectively. Note that each edge label appears at the same index of each 3-Tuple it belongs to. In the example above, the top left vertex will get a 3-Tuple (0, 1, 29) and the left-most vertex will get a 3-Tuple (0, 16, 32).

Now, there is a Hamiltonian path in G if and only if there is an ordering of 3-Tuples with dissimilarity sum
2 * (|V| - 1). This is because an ordering of 3-Tuples has that dissimilarity sum if and only if the ordering corresponds to a Hamiltonian path in G.

References and addenda

The reduction used in the proof comes from an extremely specific version of the Hamiltonian path problem. The only properties of this class of graphs (i.e. the planar, cubic, bipartite class) that are used in the proof are:

1. The graph must have chromatic index (edge coloring number) at most 3. By a result called König’s line coloring theorem, the chromatic index of bipartite graphs equals the maximum vertex degree, so a cubic bipartite graph is sufficient.
2. The 3-coloring of edges must be computable in polynomial time. In general, finding a 3-coloring of the edges of an arbitrary 3-edge-colorable graph is NP-complete. (In fact, by trying to color the vertices of the line graph, we can show it’s NP-hard to find a 4-edge-coloring of a 3-edge-colorable cubic graph with this result by Khanna et al.). To fix this, I used a result by Cole et al on Edge-Coloring Bipartite Multigraphs in O(E log D) Time. This gives a way to construct the 3-coloring on edges in polynomial (linear, actually) time on our bipartite graph.
3. The Hamiltonian path problem must be NP-hard for this class. There is a large patchwork of results on NP-completeness for Hamiltonian cycles or paths for graphs which are planar, and or cubic, and or k-connected, and or bipartite, etc. The first direct proof of the NP-completeness of Hamiltonian path on planar cubic bipartite graphs that I can cite is theorem 23 from Munaro’s paper, On line graphs of subcubic triangle-free graphs. It’s possible that an earlier reference showed this; the NP-completeness of the Hamiltonian cycle problem on that class was proven four decades earlier.