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

This is what I have so far. I created a Calc class that I can pass each of my combinations into, it then calculates the total and has a ToString() method so you don't have to worry about iterating over to output the sum string and value. You can get at the total and list passed in in the constructor. You can then just add each of your combination sets to a list which you can sort by LINQ in the inst.Total... as I have demonstrated. Still working on a means to generate each combination...

class Calc
{
    private int[] items;
    private double total;
    public double Total 
    { 
        get
        { 
            return total; 
        } 
    }
    public int[] Items
    {
        get { return items;  }
        set { total = Calculate(value); }
    }
    public static double Calculate(int[] n)
    {
        double t = 0;
        for (int i = 0; i < n.Length - 1; i++)
        {
            int a = n[i]; int b = n[i + 1];
            t += a^b;
        }
        return t;
    }
    public Calc(int[] n)
    {
        this.items = n;
        this.total = Calculate(n);
    }
    public override string ToString()
    {
        var s = String.Empty;
        for (int i = 0; i < items.Length - 1; i++)
        {
            int a = items[i]; int b = items[i + 1];
            s += String.Format("{0}^{1}", a, b);
            s += i < items.Length - 2 ? "+" : "=";
        }
        s += total;
        return s;
    }
}

And then we use the class in our calculation and very quickly sort by the totals of each permutation:

class Program
{
    static void Main(string[] args)
    {
        var Calculations = new List<Calc>();

        ////Add a new item to totals for every combination of...working on this
        Calculations.Add(new Calc(new int[] { 1, 2, 3, 4 }));
        //...

        //Grab the item with the lowest total... if we wanted the highest, we'd
        //just change .First() to .Last()
        var item = Calculations.OrderBy(i=>i.Total).First();
        Console.WriteLine(item);
        //Or if we wanted all of them:
        //Calculations.OrderBy(i=>i.Total).ForEach(Console.WriteLine);
    }
}

Answer 2

Hmm, that is an interesting problem. Using existing sorting constructs (IComparable) won't work well because you need more information than is available to the compareTo method.

The solution to this is going to be hugely dependent on what the method you want to use for sorting is. However, at first glance it would seem that you will likely have to iterate over all possible orders to find the minimum order. You could potentially short circuit it if the current sum in greater than a previous total sum.

I'll have to give this a shot and see what I can come up with.

Answer 3

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 4

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.

Answer 5

This is definitely not a sorted list. If you have a sorted list [x~0~...x~n~], the list [x~0~..x~i-1~, x~i+1~..x~n~] (i.e. x~i~ removed) will by definition also be sorted. In your example, removing the 0 from a subsequence 100,0,100 would quite likely unsort the list.

Answer 6

untested and unproven:

1. Sort the list
2. Create pairs from sorted list, grabbing the first number and the last, then the 2nd and 2nd to last, etc (i.e. 1,2,3,4 becomes 1,4 and 2,3)
3. For each pair, save it's a^b value. Reverse sort this list
4. Replace the a^b values in your new list with your a & b values

I'm guessing it can't be that simple... but it works for your example, and isn't that what really matters?

Answer 7

"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 8

This one is an NP complete problem because the algorithm is unknown (NB for the given function a^b it isn't NP Complete, it can be done by a single pass after sorting, see example below for the solution)

There is no way up front that you can generically write the "sorting algorithm" without calculating the results of the given function for all possible permutations of the list.

However once given a function, you can (possibly) devise a sorting method for that e.g. for a^b above, order the list thusly (without applying the function to any items) “Max, min, next max, next min . . .“ and reverse that order.

Depending on the complexity of the given function it will be increasingly difficult to provide optimised sorting routines.

Thanks,

Answer 9

Is that a homework assignement ?

If not, it is a dynamic programming problem. To see it, you should transform your problem into the following one using your example as a base. You are at the start. You may choose either one of {1,2,3,4}. From there you may choose to go to {1,2,3,4}. Do this 4 time and you have all the arrangement of length 4 of the list {1,2,3,4}.

Now you need a cost function, which is defined as:

f(prev, next) = prev ^ next
              = 0 if the solution is not valid for your original problem 
              = 0 if prev is the start

The total cost is expressed as

cost(i|a|X) = min(i in {1,2,3,4}, f(i, a) + cost(X))

note that i|a|X represent a list starting with an element a and then i and the rest of the list is X.

Looking at the cost function you should recognize the dynamic programing.

From there you may derive an algorithm. Look at wikipedia for an introduction to dynamic programming.

My Scheme implementation which you can test with PLT Scheme is:

(define (cost lst f)
  (if (null? lst)
      0
      (let ((h (car lst))
            (t (cdr lst)))
        (if (null? t)
            0
            (+ (f h (car t))
               (cost t f))))))

(define (solve lst f)
  (let loop ((s '()))
    (if (= (length s) (length lst))
        s
        (loop
         (let choose ((candidate lst)
                      (optimal #f)
                      (optimal-cost #f))
           (if (null? candidate)
               optimal
               (let ((c (car candidate)))
                 (if (memq c s)
                     (choose (cdr candidate) optimal optimal-cost)
                     (if (not optimal) 
                         (choose (cdr candidate) (cons c s) (cost (cons c s) f))
                         (if (<= (cost (cons c s) f)
                                 (cost optimal f))
                             (choose (cdr candidate) (cons c s) (cost (cons c s) f))
                             (choose (cdr candidate) optimal optimal-cost)))))))))))

Then calling (solve '(1 2 3 4) expt) yields another minimal solution '(3 2 1 4).

Answer 10

I only see one solution:

brute-force

    public static int Calculate(Func<int, int, int> f, IList<int> l)
    {
        int sum = 0;
        for (int i = 0; i < l.Count-1; i++)
        {
            sum += f(l[i], l[i + 1]);
        }
        return sum;
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list, int count)
    {
        if (count == 0)
        {
            yield return new T[0];
        }
        else
        {
            int startingElementIndex = 0;
            foreach (T startingElement in list)
            {
                IEnumerable<T> remainingItems = AllExcept(list, startingElementIndex);

                foreach (IEnumerable<T> permutationOfRemainder in Permute(remainingItems, count - 1))
                {
                    yield return Concat<T>(
                        new T[] { startingElement },
                        permutationOfRemainder);
                }
                startingElementIndex += 1;
            }
        }
    }

    // Enumerates over contents of both lists.
    public static IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b)
    {
        foreach (T item in a) { yield return item; }
        foreach (T item in b) { yield return item; }
    }

    // Enumerates over all items in the input, skipping over the item
    // with the specified offset.
    public static IEnumerable<T> AllExcept<T>(IEnumerable<T> input, int indexToSkip)
    {
        int index = 0;
        foreach (T item in input)
        {
            if (index != indexToSkip) yield return item;
            index += 1;
        }
    }

    public static void Main(string[] args)
    {
        List<int> result = null;
        int min = Int32.MaxValue;
        foreach (var p in Permute<int>(new List<int>() { 1, 2, 3, 4 }, 4))
        {
            int sum = Calculate((a, b) => (int)Math.Pow(a, b), new List<int>(p));
            if (sum < min)
            {
                min = sum;
                result = new List<int>(p);
            }
        }
        // print list
        foreach (var item in result)
        {
            Console.Write(item);
        }
    }

I stole the permutation code from Ian Griffiths blog.