Minimize function in adjacent items of an array

Question

I have an array (arr) of elements, and a function (f) that takes 2 elements and returns a number.

I need a permutation of the array, such that f(arr[i], arr[i+1]) is as little as possible for each i in arr. (and it should loop, ie. it should also minimize f(arr[arr.length - 1], arr[0]))

Also, f works sort of like a distance, so f(a,b) == f(b,a)

I don't need the optimum solution if it's too inefficient, but one that works reasonable well and is fast since I need to calculate them pretty much in realtime (I don't know what to length of arr is, but I think it could be something around 30)

Answer 1

You're not entirely clear what you're optimizing - the sum of the f(a[i],a[i+1]) values, the max of them, or something else?

In any event, with your speed limitations, greedy is probably your best bet - pick an element to make a[0] (it doesn't matter which due to the wraparound), then choose each successive element a[i+1] to be the one that minimizes f(a[i],a[i+1]).

That's going to be O(n^2), but with 30 items, unless this is in an inner loop or something that will be fine. If your f() really is associative and commutative, then you might be able to do it in O(n log n). Clearly no faster by reduction to sorting.

Answer 2

I don't think the problem is well-defined in this form:

Let's instead define n fcns g_i : Perms -> Reals

g_i(p) = f(a^p[i], a^p[i+1]), and wrap around when i+1 > n

To say you want to minimize f over all permutations really implies you can pick a value of i and minimize *g_i* over all permutations, but for any p which minimizes *g_i*, a related but different permatation minimizes *g_j* (just conjugate the permutation). So therefore it makes no sense to speak minimizing f over permutations for each i.

Answer 3

Unless we know something more about the structure of f(x,y) this is an NP-hard problem. Given a graph G and any vertices x,y let f(x,y) be 1 if there is no edge and 0 if there is an edge. What the problem asks is an ordering of the vertices so that the maximum f(arr[i],arr[i+1]) value is minimized. Since for this function it can only be 0 or 1, returning a 0 is equivalent to finding a Hamiltonian path in G and 1 is saying that no such path exists.

The function would have to have some sort of structure that disallows this example for it to be tractable.