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)]);
Is there an efficient algorithm that could be used to implement
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 (?).