All combination of a list of tuples

Question

I'm practicing some optimization problems and I'm stuck.

I have a list of tuples and I am doing the following:

private static int CalculateMinimumTotalCost(List<Tuple<int, int>> tuples)
{
    int minimumCost = 0;

    for(int i=0;i<tuples.Count()-1;i++)
    {
        minimumCost += Math.Max(Math.Abs(tuples[i].Item1 - tuples[i + 1].Item1), Math.Abs(tuples[i].Item2 - tuples[i + 1].Item2));
    }
    return minimumCost;
}

The idea is that given a list of tuples and this mathematical equation, I need to find the minimum cost. The catch is that the order of the tuples can be rearranged. My job is to find the LEAST costly arrangement of tuples.

So what I would like to do is loop through all possible combination of Tuples and return the combination with the minimum cost.

For example:

(1,2)(1,1)(1,3) = 3

(1,1)(1,2)(1,3) = 2

So in this case, i would return 2 because that arrangement is less costly.

I understand that when there are N tuples, the number of combinations is N!.

How do I get all the combinations possible for a list of tuples?

Thanks!

Answer 1

As other have suggested you should create the Point class:

public partial class Point
{
    public int X { get; set; }
    public int Y { get; set; }

    public Point(int x, int y)
    {
        this.X = x;
        this.Y = y;
    }
}

And, let's encapsulate the functions for computing distance and total cost :

public partial class Point
{
    public static int CalculateDistance(Point p0, Point p1)
    {
        return Math.Max(
            Math.Abs(p0.X - p1.X),
            Math.Abs(p0.Y - p1.Y)
            );
    }
}

public static class PointExtensions
{
    public static int GetTotalCost(this IEnumerable<Point> source)
    {
        return source
            .Zip(source.Skip(1), Point.CalculateDistance)
            .Sum();
    }
}

Finally, you will need another extension method to create "all possible combination" :

public static class PermutationExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> source)
    {
        if (source == null || !source.Any())
            throw new ArgumentNullException("source");

        var array = source.ToArray();

        return Permute(array, 0, array.Length - 1);
    }
    private static IEnumerable<IEnumerable<T>> Permute<T>(T[] array, int i, int n)
    {
        if (i == n)
            yield return array.ToArray();
        else
        {
            for (int j = i; j <= n; j++)
            {
                array.Swap(i, j);
                foreach (var permutation in Permute(array, i + 1, n))
                    yield return permutation.ToArray();
                array.Swap(i, j); //backtrack
            }
        }
    }
    private static void Swap<T>(this T[] array, int i, int j)
    {
        T temp = array[i];

        array[i] = array[j];
        array[j] = temp;
    }
}

Source from Listing all permutations of a string/integer adapted to be more LINQ-friendly

---

Usage :

void Main()
{
    var list = new List<Point>
    {
        new Point(1, 2),
        new Point(1, 1),
        new Point(1, 3),
    };

    // result: Point[] (3 items) : (1, 1), (1, 2), (1,3)
    list.GetPermutations()
        .OrderBy(x => x.GetTotalCost())
        .First();
}

---

EDIT : As @EricLippert pointed out, source.OrderBy(selector).First() has some extra cost. This following extension method deals with this issue :

public static class EnumerableExtensions
{
    public static T MinBy<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector, IComparer<TKey> comparer = null)
    {
        IEnumerator<T> etor = null;

        if (source == null || !(etor = source.GetEnumerator()).MoveNext())
            throw new ArgumentNullException("source");

        if (keySelector == null)
            throw new ArgumentNullException("keySelector");

        var min = etor.Current;
        var minKey = keySelector(min);

        comparer = comparer ?? Comparer<TKey>.Default;
        while (etor.MoveNext())
        {
            var key = keySelector(etor.Current);
            if (comparer.Compare(key, minKey) < 0)
            {
                min = etor.Current;
                minKey = key;
            }
        }

        return min;
    }
}

And, we can rewrite the above solution as :

list.GetPermutations().MinBy(x => x.GetTotalCost())

Answer 2

You can change the for loop to Foreach to make it more readable and rather than using index to fetch values.

private static int CalculateMinimumTotalCost(List<Tuple<int, int>> tuples)
        {
            int minimumCost = 0;
            Tuple<int, int> currentTuple = tuples.First();

            foreach (Tuple<int, int> tuple in tuples)
            {
               minimumCost += Math.Max(Math.Abs(currentTuple.Item1 - tuple.Item1), Math.Abs(currentTuple.Item2 - tuple.Item2));
               currentTuple = tuple;
            }
            return minimumCost;
        }