Minimizing the sum of a special function over a list

Question

Say I have a list and I want it arranged so that the sum of a certain function operating over its consecutive elements is minimum.

For example consider the list { 1, 2, 3, 4 } and sum a^b for consecutive pairs (a,b) over the entire list. ie. 1^2 + 2^3 + 3^4 = 90. By inspection, the minimum sum is achieved when the list is arranged as { 2, 3, 1, 4 } => (2^3 + 3^1 + 1^4 = 12).

Note that the sum is not looping (ie. I do not consider last^first) and order is important (2^3 != 3^2) and also a^b could be any function operating over any number of consecutive elements.

Is there a name for such an algorithm and is there established ways of implementing it?

EDIT: I have reworded the question since I had incorrectly labeled this as a sorting problem. As pointed out, this is more of an optimization problem.

Answer 1

"Sorting" is usually defined using a binary comparison operator ("less-than-or-equal"). What you are looking for is the "best" permutation of a list, where "best" is defined as a criterion that is defined over the whole list (while the "certain function" is defined on neighbor elements, the sum over the whole list makes it a global property).

If i understand it correctly, the "traveling salesman" is an instance of your problem, so your problem is NP-complete anyway ;-)

Answer 2

Since there's no restiction on the function used

also a^b could be any function operating over any number of consecutive elements.

if a constant function is used (say one that alwasys returns 1), the sum will be the same for all orderings, but you don't necessarily know that until you've looked at all orderings.

So I can't see anything quicker than evaluating the function-and-sum on all permutations.

(You can memoize the results for each tuple to speed up the evaluation, but I think you still need to look at them all)

EDIT: Also, since it could be a function acting on all the elements, you could have a function that returned 0 for all permutations except one, for which it returns 1.

So for the general case, you are definitely going to need to evaluate the function on all permutations.

Answer 3

It seems like this an Optimization Probelm, not a sorting problem.

I bet with with a little bit (or maybe a lot) of work someone could show this is functionally equivalent to one of the famous NP complete problems. However, for some specific functions (such as a^b in your example), the problem might be easier.