How can I optimize this combination method?

Question

I have this method that is working perfectly fine, but it's very slow, and sometimes I have to wait 15 minutes to get a good result, which is ok. I'm wondering if I can make it faster.

Basically I'm running best fleet simulations, and I pre-calculate the possible ship combinations for specific voyages, but then I have to get the best fleet combinations for multiple voyages.

Obviously I can't use the same captain or crew in different ships because the voyages take place at the same time, and that's why there's some more conditions in each inner loop.

private static Ship[] GetBestFleet3(IList<Voyage> voyages)
{
    var bestRate = 0;
    var worstVariance = 100.0;
    Ship[] fleet = null;
    foreach (var ship0 in voyages[0].Ships)
    {
        foreach (var ship1 in voyages[1].Ships.Where(s1 => !s1.Equals(ship0)))
        {
            foreach (var ship2 in voyages[2].Ships.Where(s2 => !s2.Equals(ship0) && !s2.Equals(ship1)))
            {
                var variance = Statistics.Variance(ship0, ship1, ship2);
                var rate = ship0.Rate + ship1.Rate + ship2.Rate;
                if (rate >= bestRate || rate == bestRate && variance < worstVariance)
                {
                    bestRate = rate;
                    worstVariance = variance;
                    fleet = new[] { ship0, ship1, ship2 };

                    if (ship0.Rate >= 100 && ship1.Rate >= 100 && ship2.Rate >= 100)
                    {
                        return fleet;
                    }
                }
            }
        }
    }
    return fleet;
}

voyages is basically an array of voyages with possible ship combinations for each voyage.

Gist with all the relevant project files: https://gist.github.com/alfaproject/cb68e6fa1c21e1f93bf7

Answer 1

I'd try to go with a different approach. At the moment you're evaluating all the possible combinations, while I think it could be useful to evaluate only the meaningful ones. To do that I'd start with a two phase approach. First you can generate all the valid fleets and then you can sort them using a comparator that takes into account their Range/Variance.

This is the code you can use to generate all the possible fleets:

private static IEnumerable<Fleet> PossibleVoyages(IList<Captain> captains, IList<Crew> crews, int voyagesToPrepare, Fleet fleet)
{
    var possibleVoyages = new List<Fleet>();
    if(voyagesToPrepare == 0)
    {
        possibleVoyages.Add(fleet);
    }
    if(captains.Count < voyagesToPrepare || crews.Count < voyagesToPrepare)
    {
        // We cannot find any valid solution here
        return possibleVoyages;
    }
    else
    {
        foreach(var captain in captains)
        {
            foreach(var crew in crews)
            {
                var newFleet = fleet.Add(CreateShip(captain, crew));
                possibleVoyages.AddRange(
                    PossibleVoyages(
                        FreeCaptains(captains, newFleet),
                        FreeCrews(crews, newFleet),
                        voyagesToPrepare - 1,
                        newFleet));
            }
        }
    }
    return possibleVoyages;
}

I have not implemented the methods FreeCaptains, FreeCrews, and CreateShip but they should be obvious. Fleet act as an immutable collection of ships.

Once you get all the possible voyages you can just sort them using a comparator and Linq sort.

I'm not sure this is going to help much, but it is worth giving it a try. A possible way to improve it is to keep track of the best fleet we generated so far and to just compare it with every fleet we generate instead of doing all the comparisons at the end. This could possibly prune a lot of solutions once you find a good one and it is definitely worth trying.

Answer 2

I have implemented some code to compare two ships. By doing this, you will avoid using that long statement of filtering of data. There was also a condition which was wrong.

I am still not sure why you need the explicit three loops (you know your requirements better).

var totalRate = 0;
var previousStdDev = 100.0;
Ship[] fleet = null;
IEnumerable<Ship> firstShips = voyages[0].Ships.ToList();
IEnumerable<Ship> secondShips = voyages[1].Ships.ToList();
IEnumerable<Ship> thirdShips = voyages[2].Ships.ToList();
var shipCompare = new ShipComparer();
IEnumerable<Ship> filteredFirstShips = firstShips;
IEnumerable<Ship> filteredSecondShips = secondShips.Except(filteredFirstShips, shipCompare).ToList();
IEnumerable<Ship> filteredThirdShip = thirdShips.Except(secondShips, shipCompare).ToList();
filteredThirdShip = filteredThirdShip.Except(firstShips).ToList();


foreach (var firstShip in filteredFirstShips)
{
    foreach (var secondShip in filteredSecondShips)
    {
        foreach (var thirdShip in filteredThirdShip)
        {
            var stdDev = Statistics.Variance(firstShip, secondShip, thirdShip);
            var tempSum = firstShip.Rate + secondShip.Rate + thirdShip.Rate;
            if (tempSum >= totalRate && stdDev < previousStdDev)
            {
                totalRate = tempSum;
                previousStdDev = stdDev;
                fleet = new[] { firstShip, secondShip, thirdShip };

                if (firstShip.Rate >= 100 && secondShip.Rate >= 100 && thirdShip.Rate >= 100)
                {
                    return fleet;
                }
            }
        }
    }
}

return fleet;

internal class ShipComparer : IEqualityComparer<Ship>
{
    public bool Equals(Ship x, Ship y)
    {
        return x.Captain == y.Captain && x.Crew.Intersect(y.Crew).Any();
    }

    public int GetHashCode(Ship ship)
    {
        //TODO create a unique hash code
        return int.MaxValue;
    }
}