//+------------------------------------------------------------------+
//|                                       currencyArbitrage_demo.mq5 |
//|                                        Copyright © 2018, Amr Ali |
//|                             https://www.mql5.com/en/users/amrali |
//+------------------------------------------------------------------+
#property copyright "Copyright © 2018, Amr Ali"
#property link      "https://www.mql5.com/en/users/amrali"
#property version   "1.000"
#property description "Currency arbitrage demo using my fast 'circular k-permutations' algorithm."
#property description " "
#property description "Minimum arbitrage rate:"
#property description " "
#property description "for profitable trading, you need to input values > 1.0 (e.g., 1.00008)"
#property description "in the script window to overcome spreads and commission fees."
#property description " "
#property description "for testing only, please provide values < 1.0 (e.g., 0.99966 or less)"
#property description "in the script window to display more arbitrage opportunities"
#property strict
#property script_show_inputs

#include <Permut_library.mqh>

// you could also try ring sizes 4 and 5
input int InpRingSize=3; // RingSize

                         // for profitable trading, you need to input values > 1.0 (e.g., 1.00008)
// in the script window to overcome spread and commission fees.

// for testing only, you may need to input values < 1.0 (e.g., 0.99966 or less)
// in the script window to display more arbitrage opportunities

input double InpArbitrageThreshold=0.99966; // Minimum arbitrage rate

//+------------------------------------------------------------------+

// Arbitrage is simultaneously buying and selling the same asset at
// different prices to get immediate profit.

// Arbitrage is the practice of buying an asset and selling it for
// a higher price in another market or area to take advantage of a
// difference in price. (buy low and sell high)

// Execution risk
// Triangular aribitrage oppotunities last for few milliseconds, therefore
// this type of arbitrage is only profitable for institutional traders.
// Profits from a triangular arbitrage strategy are small but consistent
// to those who are quickest to spot and act on the imbalance. Because
// this type of "risk free" tri arb is extremely time sensitive, even a
// small delay in order placement is enough to nullify any potential profit.

// Fees
// unfortunately, you have to pay fees every time you change money, and
// these would more than wipe out your profit.

// For further reading:
// https://apiaryfund.com/forum/triangular-arbitrage-basics
// https://www.kreslik.com/forums/viewtopic.php?t=307
// http://forum.vamist.ro/blog/2/entry-6-evolution-and-principles-of-the-intercross-arbitrage/

//+-----------------------------------------------------------+
// How to use exchange rates with arbitrage

// EUR/USD exchange rate is 1.1898 / 1.1899
// so, you sell 1 EUR @1.1898 USD  (Bid price)
// so, you buy  1 EUR @1.1899 USD  (Ask price)

// Convert EUR->USD
// = SELL euros
// USD units you get = EUR units x Bid
// Convert 1 unit left to right (sell pair): multiply x low rate (MODE_BID)

// Convert EUR<-USD
// = BUY euros
// EUR units you get = USD units x 1 / Ask
// Convert 1 unit right to left (buy pair): divide / high rate (MODE_ASK)
//+-----------------------------------------------------------+

#define V 8

// Priority ranking of major currencies in forex currency pairs.
// For example, EUR always comes first in all the 7 euro pairs.
// USD comes last in 4 usd pairs, and comes first in other 3 pairs.

string arrCcy[V] = {"EUR", "GBP", "AUD", "NZD", "USD", "CAD", "CHF", "JPY"};
int   mapping[V] = { 0,     1,     2,     3,     4,     5,     6,     7   };
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// My fast algorithm for k-angular currency arbitrage:

void currencyArbitrageProblem(double &graph[][V],int k)
  {
// number of arbitrage opportunities found
   int counter=0;

// array to receive circular permutations one by one
   int ring[];

// choose "k out of n currencies"
   CombinationsIterator<int>comboIt(mapping,k,ring);

// For each unordered combination of "k out of n currencies":
// 1) Consider the first currency as the starting and ending point.
// 2) Generate all (k-1)! permutations of remaining currencies.

   do
     {
      // fix the first currency of k, permute next k-1 currencies.
      PermutationsIterator<int>perm(ring,1,k-1);

      do
        {
         // store current Path weight(arbitrage rate)
         double current_pathweight=1;

         // compute current path weight
         int s = ring[0];
         int c = s;
         for(int i=1; i<k;++i)
           {
            current_pathweight*=graph[c][ring[i]];
            c=ring[i];
           }
         current_pathweight*=graph[c][s];

         // found arbitrage opportunity
         if(current_pathweight>InpArbitrageThreshold)
           {
            // print the arbitrage path that visits every currency
            // exactly once and returns back to the starting point.
            printf("#%i: arbitrage opportunity %s = %.5f",++counter,RingToString(ring,"/"),current_pathweight);

            // decode the arbitrage path
            // https://algs4.cs.princeton.edu/44sp/Arbitrage.java.html
            int st=ring[0];
            int from=st;
            int to=-1;
            current_pathweight=1;
            double stake=1000.00;
            for(int i=1; i<k;++i)
              {
               to=ring[i];
               double weight=graph[from][to];
               printf("  %7.2f %s = %7.2f %s",stake,arrCcy[from],(stake*weight),arrCcy[to]);
               stake*=weight;
               from=to;
              }
            printf("  %7.2f %s = %7.2f %s",stake,arrCcy[to],(stake*graph[to][st]),arrCcy[st]);

            // decode the currency ring
            s = ring[0];
            c = s;
            for(int i=1; i<k;++i)
              {
               printf(PairToString(graph,c,ring[i]));
               c=ring[i];
              }
            printf(PairToString(graph,c,s));

           }

        }
      while(perm.next(ring));

     }
   while(comboIt.next(ring));

   if(!counter) Print("No arbitrage opportunity");

  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// reverse mapping of int indices to currency strings
string RingToString(int &arr[],string separator=",")
  {
   int size=ArraySize(arr);
   if(!size) return "[]";
   string str= "["+arrCcy[arr[0]];
   for(int i = 1; i<size;++i)
      str+=separator+arrCcy[arr[i]];
   str+="]";
   return (str);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
string PairToString(double &graph[][V],int i,int j)
  {
   string strType,strSymb,strRate;
   double dblRate=0;

   if(i<j)
     {
      // bid (sell) prices above the diagonal line
      strType = "Sell";
      strSymb = arrCcy[i] + "/" + arrCcy[j];
      dblRate = graph[i][j];
     }

   else
     {
      // ask (buy) prices below the diagonal line
      strType = "Buy";
      strSymb = arrCcy[j] + "/" + arrCcy[i];
      dblRate = 1.0 / graph[i][j];
     }

// format the exchange rate decimals
   if(arrCcy[i]=="JPY" || arrCcy[j]=="JPY")
      strRate=StringFormat("%.3f",dblRate);
   else
      strRate=StringFormat("%.5f",dblRate);

   return StringFormat("  * %s %s at %s", strType, strSymb, strRate);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/*
 * Return the fully qualified name of a currency pair, and add it to the MarketWatch.
 * If there is no applicable symbol name, it returns the passed symbol name, unchanged.
 *
 * Some Brokers add suffixes at the end of symbol names.
 * This function is useful while you work with symbols
 * other than the current chart symbol. Also, when you
 * get symbol names from user's input, or build symbols
 * dynamically, at runtime.
 */
string SymbolSearch(string pSymb)
  {
   if(StringLen(pSymb)==0)
      return (NULL);

   string symbol_name;

/** Get symbol name from MarketWatch. */
   symbol_name=getSymbol(pSymb,true);
   if(StringLen(symbol_name) > 0) return (symbol_name);

/** Get symbol name from all. */
   symbol_name=getSymbol(pSymb,false);

/** If symbol exists, add symbol to MarketWatch. */
   if(StringLen(symbol_name)>0)
     {
      SymbolSelect(symbol_name,true);

      printf("adding symbol %s to MarketWatch.",symbol_name);

/**
		 * There is a time lag before being updated.
		 * As a workaround, sleep for 1 second.
		 */
      //		Sleep(1000);

      double bid=0.0;
      uint timeOut = 3000, start = GetTickCount();
      bool success = false;
      do
        {
         success=SymbolInfoDouble(symbol_name,SYMBOL_BID,bid);
        }
      while((!success || bid==0.0) && (GetTickCount()-start)<=timeOut && !IsStopped());

      // return fully qualified symbol name
      return (symbol_name);
     }

// cannot get fully qualified name, so return passed symbol name, unchanged.
   return (pSymb);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
string getSymbol(string pSymb,bool MarketWatch)
  {
// case-insensitive search
   StringToUpper(pSymb);

   string symbol;

   for(int i=0,max=SymbolsTotal(MarketWatch); i<max; i++)
     {
      symbol=SymbolName(i,MarketWatch);
      StringToUpper(symbol);

      if(StringFind(symbol,pSymb)>-1)
        {
         return (SymbolName(i, MarketWatch));
        }
     }

   return (NULL);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above function
void OnStart()
  {
   if(InpRingSize<2)
     {
      Alert("Error: Incorrect parameters!");
      return;
     }

   if(!TerminalInfoInteger(TERMINAL_CONNECTED))
     {
      Alert("Error: Terminal is not connected to a trade server!");
      return;
     }

// start stopwatch to benchmark
   ulong s_time=GetMicrosecondCount();

// matrix representation of exchange rates graph
   double graph[V][V];
   ArrayInitialize(graph,1);

   for(int i=0; i<V-1;++i) // row is 'base' currency
     {
      for(int j=i+1; j<V;++j) // col is 'quote' currency
        {
         //string symbol=arrCcy[i]+arrCcy[j];
         string symbol=SymbolSearch(arrCcy[i]+arrCcy[j]);
         double vbid = SymbolInfoDouble(symbol, SYMBOL_BID);
         double vask = SymbolInfoDouble(symbol, SYMBOL_ASK);

         // cache exchange rates in a matrix for efficiency
         // V^2 cells = V.(V - 1) prices + V diagonal cells
         // bid (sell) prices above the diagonal line
         // ask (buy) prices below the diagonal line
         graph[i][j] = vbid;        // eur->usd
         graph[j][i] = 1.0 / vask;  // eur<-usd
        }
     }

   int n = ArraySize(arrCcy);
   int k = InpRingSize;

   currencyArbitrageProblem(graph,k);

// count of circular k-permutations = nPk / k
   printf("Done! examined all the %I64i possible arbitrage rings with %i currencies taken from %i. (%i microseconds)",nPk(n,k)/k,k,n,(GetMicrosecondCount()-s_time));
  }
//+------------------------------------------------------------------+