How best to calculate derived currency rate conversions using C#/LINQ?

 class FxRate {
     string Base { get; set; }
     string Target  { get; set; }
     double Rate { get; set; }
 }

 private IList<FxRate> rates = new List<FxRate> {
          new FxRate {Base = "EUR", Target = "USD", Rate = 1.3668},
          new FxRate {Base = "GBP", Target = "USD", Rate = 1.5039},
          new FxRate {Base = "USD", Target = "CHF", Rate = 1.0694},
          new FxRate {Base = "CHF", Target = "SEK", Rate = 8.12}
          // ...
 };

Given a large yet incomplete list of exchange rates where all currencies appear at least once (either as a target or base currency): What algorithm would I use to be able to derive rates for exchanges that aren't directly listed?

I'm looking for a general purpose algorithm of the form:

 public double Rate(string baseCode, string targetCode, double currency)
 {
      return ...
 }

In the example above a derived rate would be GBP->CHF or EUR->SEK (which would require using the conversio开发者_如何学运维ns for EUR->USD, USD->CHF, CHF->SEK)

Whilst I know how to do the conversions by hand I'm looking for a tidy way (perhaps using LINQ) to perform these derived conversions perhaps involving multiple currency hops, what's the nicest way to go about this?

First construct a graph of all your currencies:

private Dictionary<string, List<string>> _graph
public void ConstructGraph()
{
    if (_graph == null) {
        _graph = new Dictionary<string, List<string>>();
        foreach (var rate in rates) {
            if (!_graph.ContainsKey(rate.Base))
                _graph[rate.Base] = new List<string>();
            if (!_graph.ContainsKey(rate.Target))
                _graph[rate.Target] = new List<string>();

            _graph[rate.Base].Add(rate.Target);
            _graph[rate.Target].Add(rate.Base);
        }
    }
}

Now traverse that graph using recursion:

public double Rate(string baseCode, string targetCode)
{
    if (_graph[baseCode].Contains(targetCode)) {
        // found the target code
        return GetKnownRate(baseCode, targetCode);
    }
    else {
        foreach (var code in _graph[baseCode]) {
            // determine if code can be converted to targetCode
            double rate = Rate(code, targetCode);
            if (rate != 0) // if it can than combine with returned rate
                return rate * GetKnownRate(baseCode, code);
        }
    }

    return 0; // baseCode cannot be converted to the targetCode
}
public double GetKnownRate(string baseCode, string targetCode) 
{
    var rate = rates.SingleOrDefault(fr => fr.Base == baseCode && fr.Target == targetCode);
    var rate_i rates.SingleOrDefault(fr => fr.Base == targetCode && fr.Target == baseCode));
    if (rate == null)
        return 1 / rate_i.Rate
    return rate.Rate;
}

Disclaimer: This is untested. Further, I'm sure this isn't the most performant approach to solve the problem (O(n) I think), but I believe it will work. There are a number of things you could add to improve the performance (e.g. saving every new combined rate calculation would eventually turn this into an effective O(1))

Wouldn't it be simpler to just have a list of all conversions to a single currency and then use that for any conversion? So something like (with USD as the base currency):

var conversionsToUSD = new Dictionary<string, decimal>();

public decimal Rate ( string baseCode, string targetCode )
{
    if ( targetCode == "USD" )
        return conversionsToUSD[baseCode];

    if ( baseCode == "USD" )
        return 1 / conversionsToUSD[targetCode];

    return conversionsToUSD[baseCode] / conversionsToUSD[targetCode]
}

Now, this assumes that algebra is perfectly communicative. I.e., if I convert to EUR->USD->GBP I'll get the same as converting from EUR->GBP. That might not actually be the case in reality in which case, you would need every supported permutation.

Interesting problem!

First off, stay clear from double / floating point arithmetic. The .NET Decimal type should be quite sufficient and provide better precision! Such improved precision may be particularly important given the fact that the calculation of derived Fx rates requires a chain of multiple operations.

Another remark is that it is probably off-limits to introduce a simpler/shorter list of Exchange rates, whereby the Target is always the same [real or fictitious] currency. I'm assuming here that we should use the listed rate when available.

So figuring out derived rates should become a [simplified] network solution, whereby

• Given a Base and Target currencies, we identify all the shortest pathes (from Base to Target), given the authoritative (non derived) rates in the list. (We can hope that the shortest path would be 2, in all cases, but this may not be the case given very esoteric currencies).
• for each of these shortest paths (I think it would be ludicrous to also consider longer pathes), we perform the simple arithmetic conversion, and...
• hopefully confirm that these derived rates are all within a nominal margin of conversion error and therefore take the average of these rates
• raise some alert... or just make a lot of money by using making a circular path and raking in the differential ;-)

I have no idea what that "double currency" is for... i'll just ignore it.

Attempt: List<List<FxRate>> res = Rates("EUR", "CHF"); yields {EUR-USD, USD-CHF}.
Looks promising! :)

    public class FxRate
    {
        public string Base { get; set; }
        public string Target { get; set; }
        public double Rate { get; set; }
    }

    private List<FxRate> rates = new List<FxRate>
                                    {
                                        new FxRate {Base = "EUR", Target = "USD", Rate = 1.3668},
                                        new FxRate {Base = "GBP", Target = "USD", Rate = 1.5039},
                                        new FxRate {Base = "USD", Target = "CHF", Rate = 1.0694},
                                        new FxRate {Base = "CHF", Target = "SEK", Rate = 8.12}
                                        // ...
                                    };

    public List<List<FxRate>> Rates(string baseCode, string targetCode)
    {
        return Rates(baseCode, targetCode, rates.ToArray());
    }
    public List<List<FxRate>> Rates(string baseCode, string targetCode, FxRate[] toSee)
    {
        List<List<FxRate>> results = new List<List<FxRate>>();

        List<FxRate> possible = toSee.Where(r => r.Base == baseCode).ToList();
        List<FxRate> hits = possible.Where(p => p.Target == targetCode).ToList();
        if (hits.Count > 0)
        {
            possible.RemoveAll(hits.Contains);
            results.AddRange(hits.Select(hit => new List<FxRate> { hit }));
        }

        FxRate[] newToSee = toSee.Where( item => !possible.Contains(item)).ToArray();
        foreach (FxRate posRate in possible)
        {
            List<List<FxRate>> otherConversions = Rates(posRate.Target, targetCode, newToSee);
            FxRate rate = posRate;
            otherConversions.ForEach(result => result.Insert(0, rate));
            results.AddRange(otherConversions);
        }
        return results;
    }

Comments?

PS: you can get the cheaper convertion with double minConvertion = res.Min(r => r.Sum(convertion => convertion.Rate));

The most straight-forward algorithm would probably just be like Dijkstra's shortest path or something on a graph you generate using that list. Being that you don't know beforehand how long the path will be, this isn't really a problem that can be elegantly solved by a LINQ query. (Not that it's not possible, it's just probably not what you should pursue.)

On the other hand, if you know that there is a path from any currency to any other, and that there is only one possible conversion between any two currencies on the list (ie, if USD > EUR and USD > CHF exist, then EUR > CHF doesn't exist or you can ignore it), you can simply generate something like a doubly linked list and traverse. Again though, this isn't something that can be elegantly solved through LINQ.

Generate all of them and cache them. Given initial set this function will generate all existing pairs (inside same list) without graphs or recursion, by simple expanding initial list as it iterates.

public static void CrossRates(List<FxRate> rates)
{
    for (int i = 0; i < rates.Count; i++)
    {
        FxRate rate = rates[i];
        for (int j = i + 1; j < rates.Count; j++)
        {
            FxRate rate2 = rates[j];
            FxRate cross = CanCross(rate, rate2);
            if (cross != null)
                if (rates.FirstOrDefault(r => r.Ccy1.Equals(cross.Ccy1) && r.Ccy2.Equals(cross.Ccy2)) == null)
                    rates.Add(cross);
        }
    }
}

This utility function will generate individual cross rate.

public static FxRate CanCross(FxRate r1, FxRate r2)
{
    FxRate nr = null;

    if (r1.Ccy1.Equals(r2.Ccy1) && r1.Ccy2.Equals(r2.Ccy2) ||
        r1.Ccy1.Equals(r2.Ccy2) && r1.Ccy2.Equals(r2.Ccy1)
        ) return null; // Same with same.

    if (r1.Ccy1.Equals(r2.Ccy1))
    { // a/b / a/c = c/b
        nr = new FxRate()
        {
            Ccy1 = r2.Ccy2,
            Ccy2 = r1.Ccy2,
            Rate = r1.Rate / r2.Rate
        };
    }
    else if (r1.Ccy1.Equals(r2.Ccy2))
    {
        // a/b * c/a = c/b
        nr = new FxRate()
        {
            Ccy1 = r2.Ccy1,
            Ccy2 = r1.Ccy2,
            Rate = r2.Rate * r1.Rate
        };
    }
    else if (r1.Ccy2.Equals(r2.Ccy2))
    {
        // a/c / b/c = a/b
        nr = new FxRate()
        {
            Ccy1 = r1.Ccy1,
            Ccy2 = r2.Ccy1,
            Rate = r1.Rate / r2.Rate
        };
    }
    else if (r1.Ccy2.Equals(r2.Ccy1))
    {
        // a/c * c/b = a/b
        nr = new FxRate()
        {
            Ccy1 = r1.Ccy1,
            Ccy2 = r2.Ccy2,
            Rate = r1.Rate * r2.Rate
        };
    }
    return nr;
}