Closest permutations

Question

I have currently have two lists of 4 3D points, let us call the lists A and B. I want to connect each point in A to one (and only one) point in B such that the total distance between A and B is minimised.

So for example if I have:

A 1: (0,0,0) 2: (0,10,0) 3: (0,20,0) 4: (0,30,0)

B 1: (0,35,10) 2: (0,25,10) 3: (0,15,10) 4: (0,5,10)

The optimal solution would be to connect A1 with B4, A2 with B3, A3 with B2 and A4 with B1.

How would I go about computing this in a reasonable way?

Answer 1

When the number of items is small, as it is in your case, you can do this by bruteforcing all permutations in three nested loops:

Point3D[] a = new Point3D[4];
Point3D[] b = new Point3D[4];
for (int i = 0 ; i != 4 ; i++) {
    for (int j = 0 ; j != 4 ; j++) {
        if (j == i) continue;
        for (int k = 0 ; k != 4 ; k++) {
            int m = 6 - i - j - k;
            if (k == i || k == j || m == i || m == j || m == k) continue;
            var d = a[0].Distance(b[i]) +a[1].Distance(b[j]) + a[2].Distance(b[k]) + a[3].Distance(b[m]);
            min = Math.Min(d, min);
        }
    }
}

This finds the minimum in 4! = 24 iterations. If you have more points than, say, more than ten, a much better algorithm is available - you can use the Hungerian algorithm to find the minimum-weight matching in polynomial time O(n³).

Answer 2

    public static IEnumerable<Result> Connect(this IEnumerable<Point> setA, IEnumerable<Point> setB) {
        return setA
            .Select(a => setB.Select(b => new Result { A = a, B = b, D = a.DistanceTo(b) }))
            .SelectMany(s => s)
            .OrderBy(s => s.D)
            .Reduce(new Result[] { }, (a,b) => a.A != b.A && a.B != b.B);
    }

using:

    public static IEnumerable<T> Concat<T>(this T h, IEnumerable<T> t) {
        yield return h;
        foreach (var r in t) {
            yield return r;
        }
    }

    static IEnumerable<T> Reduce<T>(this IEnumerable<T> items, IEnumerable<T> collected, Func<T,T,bool> predicate) {
        if (!items.Any())
            return new T[0];

        var t = items.First();
        var filtered = items.Where(s => predicate(s,t));
        return t.Concat(filtered.Reduce(t.Concat(collected), predicate));
    }

where

struct Result {
    public Point A;
    public Point B;
    public double D;//distance
}

struct Point {
    public int X;
    public int Y;
    public int Z;
}

double DistanceTo(this Point a, Point b) {
    return Math.Sqrt((a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y) + (a.Z - b.Z) * (a.Z - b.Z));
}