Minimize sum of adjacent element differences of array by reordering

help
1

Let's say I have an array of tuples:

let a = [(1,3), (4,0), (0,4), (3,1), (2,2)];

My goal is to rearrange the elements in the array such that the total sum of all differences between two adjacent elements is minimized. The difference of two tuples is, in this case, defined to be the sum of the differences between both elements (abs_diff(l.0, r.0) + abs_diff(l.1, r.1)), but could be defined differently. In this case it is fairly self-evident that the following two solutions are both optimal:

assert_eq!(minimize_diffs(&a), [(0,4), (1,3), (2,2), (3,1), (4,0)]);
// or: assert_eq!(minimize_diffs(&a), [(4,0), (3,1), (2,2), (1,3), (0,4)]);

Question:

Is there an efficient algorithm that could be used to implement minimize_diffs()?

Real-life background / XY problem

I am trying to organize a (physical) bookshelf of books I only rarely need. Thus, I concluded that visual appeal matters the most, which I am trying to realize by sorting the books by color. Since color, unlike e.g. height, is multi-dimensional, there isn't one obvious way to sort them. I concluded that an approach like the above would be the best option, but this conclusion may be wrong. The amount of books I am trying to sort this way is over 100 btw, making any non-polynomial approach infeasible (?).

2

I don't believe this problem is solvable in polynomial time. If you map each book to a node and the difference between the books as weights on their edges, this becomes a bijection of the Traveling Salesman problem, which is NP-complete.

Granted, the TSP is quite well-studied, so if a heuristic (non-optimal) solution is acceptable, it's certainly possible to come up with one in a reasonable time. The most effective way of implementing a solution of this problem from a developer-time standpoint would be to reduce it to a case of TSP or to an integer-linear program and then chuck it at a solver written by people paid money to build these sorts of solvers.

If you want to roll your own solution, I would first recommend trying a simulated annealing approach. Let me know if you'd like me to clarify further.

2 Likes
3

The higher-dimensional data can be reduced to a single dimension with a space-filling curve. But I don't know which colorspaceĀ¹ and curve yield nice results for your problem.

Ā¹ Thoguh generally CIELab and similar perceptual metrics are often used for these kinds of problems.

2 Likes
4

Equivalence to the TSP seems clear to me at second glance, I should perhaps take a closer look at heuristics regarding that. Regarding the simulated annealing approach: What is a 'neighbor' of a list of colors? Does it mean that a random element is swapped with its left/right neighbor or something different?

5

I was planning to use the Oklab perceptual color space, but I don't think any space-filling curve could really fulfill what I am trying to do: e.g. if one dimension strictly increases and another strictly decreases (as presented in the above example), the values shall be sorted according to this metric, while any other combination of differences should impact the result in the same way. I don't think any space-filling curve could, by definition, be symmetric over all input dimensions, but I could also be wrong.

6

The neighboring state would actually be a differing permutation of your bookshelf. In your case, I would recommend something that looks like the following:

  1. Select two books at random from the shelf.
  2. Compute the expected increase in cost delta_c and some random fudge factor f based on the current iteration.
  3. If delta_c - f < 0, swap the books.

Repeat until you're happy with the result. A decent fudge factor is just a random number with exponentially decreasing variance with each iteration.

1 Like