Combinatorics in MQL5

[Versiunea romaneasca] [MQLmagazine.com in romana] [English edition]

Long time ago I wrote on my former blog about generation of permutations, however I never dwelved too much into explaining the algorithm and the code. Indeed, there are situations when combinatorics are to be applied – when scouting for arbitrages or while deploying statistics requiring asset selections as prerequisite.

Permutations

Permutations are quite simple to both find and generate, although math manuals quite skip these algorithms. Since permutations are specific orders in which elements of a set are arranged, that means while arranging the elements, the possibilities to arrange the remainder elements shrink. For instance if we have 4 elements in a set, after setting the first we have just 3 places left, and so on, until the last element fits automatically to the single place left. Thus, the composition of the number depicting the permutation number is done like when composing a number in another numeration base, except that the base shrinks at every step.

For instance we have to find this permutation’s number:

|1|2|3|4|
|1|4|2|3|

At the beginning, the numeration base is 4, and our array is empty:

|1|2|3|4| : mathematical notation of positions
|1|4|2|3| : permutation to decypher

|0|0|0|0| : occupied places in the array
|0|1|2|3| : places in the array (zero-based)
|0|1|2|3| : count array

We look on the first position, 1, and read the first element, “1″. For computing reasons we use zero-based arrays.
Permutation number = 1-1 = 0

|1|2|3|4| : mathematical notation of positions
|1|4|2|3| : permutation to decypher

|0|0|0|0| : presently occupied places in the permutation
|1|0|0|0| : occupied places in positions notation after insertion
|0|1|2|3| : count array (conceptual, for counting)
|x|0|1|2| : new count array for remainder elements

Now we look at the second element. The second element reads “4″. Then, as we have just 3 seats free, the numeration base is 3. Permutation number = (0 x 3) = 0. To this, we add the position in the count array for the element “4″, which is 2 : Permutation number = 0 + 2 = 2

|1|2|3|4| : mathematical notation of positions
|1|4|2|3| : permutation to decypher

|1|0|0|0| : presently occupied places in the notation of positions
|1|0|0|4| : occupied places in positions notation after insertion
|x|0|1|2| : count array
|x|0|1|x| : new count array for remainder elements

Now we look at the third element. The third element reads “2″. Then, as we have just 2 seats free, the numeration base is 2. Permutation number = (2 x 2) = 4. To this, we add the position in the count array for the element “2″, which is 0 : Permutation number = 4 + 0 = 4

|1|2|3|4| : mathematical notation of positions
|1|4|2|3| : permutation to decypher

|1|0|0|4| : presently occupied places in the notation of positions
|1|2|0|4| : occupied places in positions notation after insertion
|x|0|1|2| : count array
|x|x|0|x| : new count array for remainder elements

Calculation stops. We need only to insert in calculation n-1 elements. The nth element is presumed to be on the leftover place.

Final permutation number = 4

The reverse algorithm, to generate permutations from permutation numbers, is the following:
Starting from base 2, we do n-1 steps of dividing the previous result by an increasing base, keeping the remainder.
So we have:
4 / 2 = [2], remainder 0
[2] / 3 = 0, remainder 2
[0] / 4 = 0, remainder 0

Then we start building the permutation back. We read the last remainder, and we find it to be 0. This means our first element is indeed “1″, as 0 from the count array stands for 1 in the positions array.

|1|2|3|4| : mathematical notation of positions
|0|1|2|3| : physical subscripts in array variable
|0|1|2|3| : count array
|1|0|0|0| : occupied positions after current element insertion
|x|0|1|2| : new count array for remainder elements
|1|0|0|0| : built permutation

Our base shrinked to 3, as we have 3 seats left. We read the following remainder, in a reversed order, and we find it to be 2. Looking into the new count array, we see that 2 corresponds to element “4″ from the mathematical notation.

|1|2|3|4| : mathematical notation of positions
|0|1|2|3| : physical subscripts in array variable
|x|0|1|2| : count array
|1|0|0|4| : occupied positions after current element insertion
|x|0|1|x| : new count array for remainder elements
|1|4|0|0| : built permutation

Our base shrinked to 2, as we have 2 seats left. We read the following remainder, in a reversed order, and we find it to be 0. Looking into the new count array, we see that position 0 corresponds to element “2″ from the mathematical notation.

|1|2|3|4| : mathematical notation of positions
|0|1|2|3| : physical subscripts in array variable
|x|0|1|x| : count array
|1|2|0|4| : occupied positions after current element insertion
|x|x|0|x| : new count array for remainder elements
|1|4|0|2| : built permutation

We have only last element to be determined, and that is “3″, on the single free seat unoccupied.

|1|2|3|4| : mathematical notation of positions
|0|1|2|3| : physical subscripts in array variable
|x|x|0|x| : count array
|1|2|3|4| : occupied positions after current element insertion
|x|x|x|x| : new count array for remainder elements
|1|4|3|2| : built permutation

Because both algorithms are quite straight, they can be implemented straight into functions. Thus, we are starting to write the Combinatorics.mqh.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//+------------------------------------------------------------------+
//|                                                Combinatorics.mqh |
//|                                       Copyright Bogdan Caramalac |
//|                                           http://mqlmagazine.com |
//+------------------------------------------------------------------+
#property copyright "Copyright Bogdan Caramalac"
#property link      "http://mqlmagazine.com"
 
//*************************************************
 
 string Replicate(string s, int count)
   {
    string res="";
    if (count<=0)
      return(res);
    for (int i=1;i<=count;i++)
      StringConcatenate(res,res,s);
    return(res);
   }
 
 int MathDiv(int a,int b)
    {
     int res;
     res=a-MathRound(MathMod(a,b));
     res=MathRound(res/b);
     return(res);
    }
 
 int Round(double a)
    {
     return(MathRound(NormalizeDouble(a,0)));
    }
 
//*************************************************

Usual stuff that we don’t insist on, we go forward to Permutations:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//********************************************************************
//
//
//                             Permutations
//
//
//********************************************************************
 
 long Factorial(ushort n)
   {
    long res=1;
    for (int i=2;i<=n;i++)
       res=res*i;
    return(res);
   }
 
 int FindPermutation(ushort elem, int& perm[])
    {
     int res=0;
     int rr;
     int positions[30];
     for (int i=0;i<ArrayRange(positions,0);i++)
        positions[i]=i+1;
     for (int e=1;e<elem;e++)//we don`t look for the last element , there is one seat left
        {
         rr=0;
         for (int i=0;i<elem;i++)
            {
             if (perm[e-1]==i+1)
               {
                res=res+rr;//has already -1, it`s zero-based
                //Print("Found element ",perm[e-1]," to be on perm[",i,"]. Adding ",rr, " to res, equals ",res);
                if (e!=elem-1)
                  res=res*(elem-e);
                //Print("Multiplicating by elem-e (",elem-e,") = ",res);                
                positions[i]=-1;
               }
             else
               { //if the searched element is not on current element,
                 //increment place counter only current position was not previously used;
                if (positions[i]!=-1)
                  rr++;
               }
            }
        }//for (int e=1;i<=elem;i++)
      return(res);  
    }
 
void GeneratePermutation(int number,int elem,int &perm[])
    {    
    string elemallow; 
    int stoppoint,crtpoint;       
    ushort AscX=StringGetCharacter("X",0);
    int i,j,base;
    int nnow;
    elemallow=Replicate("a",20);
    base=2;    
    nnow=number;    
    for (i=elem-2;i>=0;i--)
       {
       perm[i]=Round(MathMod(nnow,base));       
       nnow=MathDiv(nnow,base);
       base=base+1;        
       }
    perm[0]=perm[0]+1;//because first element is from 1 to elem, not 0 to elem-1    
    for (i=0;i<=elem-2;i++)
       {
       if (i==0)
         {
          StringSetCharacter(elemallow,perm[0]-1,AscX);
         }             
       else
          {
          stoppoint=perm[i]+1;          
          crtpoint=0;
          for (j=0;j<elem;j++)
             {             
             if (StringGetCharacter(elemallow,j)==AscX)
                continue;
             else
                {
                crtpoint=crtpoint+1;
                if (crtpoint==stoppoint)
                   {
                   perm[i]=j+1;//write new perm[i]
                   StringSetCharacter(elemallow,j,AscX);
                   }                   
                }
             }//for (j=0;j<elem;j++);
          }//else if (i=0)    
        }//for (i=0;i<elem-2;i++)
    for (i=1;i<=elem;i++)
       {
       if (StringGetCharacter(elemallow,i-1)!=AscX)
          {          
          perm[elem-1]=i;          
          break;
          }
       }        
    return;  
    }

This time we got lucky. Just two simple functions to call. Won’t be the case for Combinations.

Combinations

The combinations algorithm is way harder to understand than the permutations algorithm. The most used algorithm is the one that generates combinations in a recursive manner.

Let’s look at a simple combination queue: C(5,3)

1, 2, 3
1, 2, 4
1, 2, 5
1, 3, 4
1, 3, 5
1, 4, 5

First of all, every element has a different freedom degree. For instance, first can’t be beyond n-k+1.
Another thing, is that after you generate the first element, what you have to do then are C(n-1,k-1).
For instance, C(4,2) are:

1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

For each instance of these , C(3,1) are:

1
2
3

Now you can see how it integrates:

When the procedure is called to generate C(5,3) it starts enumerating the first element, from 1 to 3. Thus, it has:

1,(1+x)

Then it calls itself to generate C(4,2) , starts enumerating from 1 to 2.
1,(1+1),(2+x)

Finally calls itself to generate C(3,1) , and completes:
1,2,(2+1) = 1,2,3
1,2,(2+2) = 1,2,4
1,2,(2+3) = 1,2,5

Returns to the previous cycle and continues with C(4,2) with the following element, 2:
1,(1+2),(1+2+x)

Starts calling C(3,1) and completes
1,3,4
1,3,5

Then turns back to continue C(5,3) with the following element, 2.

The algorithm continues until first function call ends the enumeration loop.

The implementation of the algorithm is quite murky. This time we opted for a class. Because, since direct generation is not possible, it’s not feasible to generate all the combinations every time you want a certain combination, in the case when you may want some from a list. So, a class is needed, to provide an inner loop generating the combinations while calling a callback function to pass the user the found combinations, with the option of early terminating.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//********************************************************************
//
//
//                             Combinations
//
//
//********************************************************************
 
 
long CombinationsTotal(ushort n,ushort k)
  {
   return(Factorial(n)/(Factorial(k)*Factorial(n-k)));
  }
 
class CombinationObject
  {   
   protected: 
   long counter;
   ushort n,k;
   bool terminate;   
   ushort current_combination[];
   private:
   ushort last_combination[];
   bool found;
 
   long CombinationsTotal(ushort n,ushort k);
   string CombImage(ushort &ccomb[],ushort n);
   void GenCombinationsRec(ushort depth,ushort nn,ushort kk);
 
   public:
   void SetupCombinationObject(ushort nn,ushort kk); 
   void LoopCombinations();
   virtual void CombinationsCallback();
   CombinationObject() {SetupCombinationObject(6,3);};   
  };
 
void CombinationObject::CombinationsCallback()
  {
   Print(CombImage(current_combination,k));
  }
 
void CombinationObject::SetupCombinationObject(ushort nn,ushort kk)
  {
   n=nn;
   k=kk;
   terminate=false;
   ArrayInitialize(current_combination,0);
   ArrayInitialize(last_combination,0);
   ArrayResize(current_combination,n);
   ArrayResize(last_combination,n);
   counter=0;
  }
 
string CombinationObject::CombImage(ushort &ccomb[],ushort n)
  {
   string res="";
   for (int i=0;i<n;i++)
      res=res+DoubleToString(ccomb[i],0)+" ";
   return(res);
  }
 
void CombinationObject::GenCombinationsRec(ushort depth,ushort nn, ushort kk)
  {
   bool okay,r;
   if (terminate==true)
     return;
 
   if (depth==k)
     return;  
 
   if (kk==0)
     return;
 
   int allows=nn-kk+1; 
   for (ushort i=1;i<=allows;i++)
      {
       if (terminate==true)
          return;
       if (depth==0)
         current_combination[depth]=i;
       else
         current_combination[depth]=current_combination[depth-1]+i;
 
       GenCombinationsRec(depth+1,nn-i,kk-1);
 
       okay=false;//checking for identical combination
       for (int j=1;j<=k;j++)
          {
           if (current_combination[j-1]!=last_combination[j-1])
             okay=true;//okay, new one
          }
       if (okay==false)
         continue;
       else
         { //copying current to last
          for (int j=1;j<=k;j++)
             last_combination[j-1]=current_combination[j-1];
         }
 
       CombinationsCallback();
       if (terminate==true)
         return;      
       counter=counter+1;
 
      }//for (int i=1;i<=allows;i++)
   return;
  }
 
void CombinationObject::LoopCombinations()
  {
   GenCombinationsRec(0,n,k);
   return;
  }

This is a way tougher nut to crack. The interesting function here, the engine itself, is GenCombinationsRec(). The depth parameter tells the function on which level it starts generating the combinations. When depth is depleted, that is, at every end of subsequent call queue, a new combination is generated in current_combination[] and counter is increased. What the user has to do, is to inherit this class in a custom class and override the CombinationsCallback(). Also, the terminate variable is available, if that is set to true, once the CombinationsCallback() ends, all GenCombinationsRec() calls will be early terminated and program will resume execution.

Arrangements

Since arrangements are permutated combinations, there is no point in overcomplicating the issue. The class is almost a carbon copy of the CombinationObject class, with the difference that the recursive method here, GenArrangementsRec(), which is quite like GenCombinationsRec(), generates combinations, and then, when every one of them is ready, permutates it and serves every arrangement (permutated combination) to the ArrangementsCallback(). Simple and convenient, yet results are not in the sorted manner like with Permutations and Combinations:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//********************************************************************
//
//
//                             Arrangements
//
//
//********************************************************************  
 
long ArrangementsTotal(ushort n,ushort k)
  {
   return(Factorial(n)/Factorial(n-k));
  }
 
class ArrangementObject
  {
   protected: 
   long counter;
   ushort n,k;
   ushort current_arrangement[];
   bool terminate;  
   private:
   ushort current_combination[];  
   ushort last_combination[];     
   bool found;
 
   long ArrangementsTotal(ushort n,ushort k);
   string ArrgImage(ushort &ccomb[],ushort n);
   void GenArrangementsRec(ushort depth,ushort nn,ushort kk);
 
 
   public:
   void SetupArrangementObject(ushort nn,ushort kk); 
   void LoopArrangements();
   virtual void ArrangementsCallback();
   ArrangementObject() {SetupArrangementObject(6,3);};   
  };
 
void ArrangementObject::ArrangementsCallback()
  {
   Print(ArrgImage(current_arrangement,k));
  }
 
void ArrangementObject::SetupArrangementObject(ushort nn,ushort kk)
  {
   n=nn;
   k=kk;
   terminate=false;   
   ArrayInitialize(current_arrangement,0);
   ArrayInitialize(current_combination,0);
   ArrayInitialize(last_combination,0);
   ArrayResize(current_combination,n);
   ArrayResize(current_arrangement,n);
   ArrayResize(last_combination,n);   
   counter=0;
  }
 
 
 
string ArrangementObject::ArrgImage(ushort &ccomb[],ushort n)
  {
   string res="";
   for (int i=0;i<n;i++)
      res=res+DoubleToString(ccomb[i],0)+" ";
   return(res);
  }
 
void ArrangementObject::GenArrangementsRec(ushort depth,ushort nn, ushort kk)
  {
   int perm[30];
   bool okay,r;
   if (terminate==true)
     return;
 
   if (depth==k)
     return;  
 
   if (kk==0)
     return;
 
   int allows=nn-kk+1; 
   for (ushort i=1;i<=allows;i++)
      {
       if (terminate==true)
          return;
       if (depth==0)
         current_combination[depth]=i;
       else
         current_combination[depth]=current_combination[depth-1]+i;
 
       GenArrangementsRec(depth+1,nn-i,kk-1);
 
       okay=false;//checking for identical combination
       for (int j=1;j<=k;j++)
          {
           if (current_combination[j-1]!=last_combination[j-1])
             okay=true;//okay, new one
          }
       if (okay==false)
         continue;
       else
         { //copying current to last
          for (int j=1;j<=k;j++)
             last_combination[j-1]=current_combination[j-1];
         }
 
 
       //here combination is final and arrangements are generated       
       for (int iperm=0;iperm<Factorial(k);iperm++)
          {
           GeneratePermutation(iperm,k,perm);           
           for (int jperm=0;jperm<k;jperm++)
              {
               current_arrangement[jperm]=current_combination[perm[jperm]-1];                              
              }                      
           ArrangementsCallback();                        
           if (terminate==true)
             return;      
           counter=counter+1;   
          }   
 
       }//for (int i=1;i<=allows;i++)
   return;                   
  }
 
void ArrangementObject::LoopArrangements()
  {
   GenArrangementsRec(0,n,k);
   return;
  }

And now a sample script (combtest.mq5). The script will display arrangements of n forex pairs taken as k, with a rising k, from 3 to n. Forex pairs are extracted at the beginning, by interogating each tradeable instrument about its calculation mode and retaining only the ones answering SYMBOL_CALC_MODE_FOREX , with the specification that symbol has to have 6 or more letters (two forex pairs and a suffix). Pairs are extracted and added to an array. Then a customized arrangements engine is called to display arrangements:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//+------------------------------------------------------------------+
//|                                                     combtest.mq5 |
//|                                       Copyright Bogdan Caramalac |
//|                                           http://mqlmagazine.com |
//+------------------------------------------------------------------+
#property copyright "Copyright Bogdan Caramalac"
#property link      "http://mqlmagazine.com"
#property version   "1.00"
 
 
#include <Combinatorics.mqh>
 
int CurrenciesCount;
int PairsCount;
string ForexPairs[100];
 
//our class: we needed it to override ArrangementsCallback;
class LocalArrgClass : public ArrangementObject
  { 
    void ArrangementsCallback()
     {
      string image="";
      image=DoubleToString(counter,0)+" :";
      for (int i=0;i<k;i++)         
         image=image+" "+ForexPairs[current_arrangement[i]-1];
      Print(image);      
     }   
  };
 
//the arrangment object
LocalArrgClass myarrg;
 
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
 
void CheckAndAddPair(string pair)
  {
   bool found;
   if (PairsCount==0)
     {
      ForexPairs[PairsCount]=pair;
      PairsCount++;
     }
   else
     {
      found=false;
      for (int i=0;i<PairsCount;i++)
         {
          if (ForexPairs[i]==pair)
            {
             found=true;
             break;
            }          
         }
      if (found==false)
        {
         ForexPairs[PairsCount]=pair;
         PairsCount++;               
        } 
     } 
   return;
  }
 
void OnStart()
  {  
   string crtsymbol,pair1,pair2;
   CurrenciesCount=0;
   PairsCount=0;
   for (int i=0;i<SymbolsTotal(false);i++)
      {
       crtsymbol=SymbolName(i,false);
       if (SymbolInfoInteger(crtsymbol,SYMBOL_TRADE_CALC_MODE)==SYMBOL_CALC_MODE_FOREX&&StringLen(crtsymbol)>=6)
         {          
          pair1=StringSubstr(crtsymbol,0,3);          
          CheckAndAddPair(pair1);
          pair2=StringSubstr(crtsymbol,3,3);         
          CheckAndAddPair(pair2);
         }
      }//for (int i=0;i<SymbolsTotal(false);i++)        
    for (int iarrg=3;iarrg<=PairsCount;iarrg++)
       {
        myarrg.SetupArrangementObject(PairsCount,iarrg);
        myarrg.LoopArrangements();      
       }
  }
//+------------------------------------------------------------------+

Here’s a peek on how it looks (though you have to stop it using terminate – otherwise it will jump some of the log):

You might ask why did we opted for permutations to use int instead of uint or long. The answer is the MathMod() and MathRound() issue. These functions don’t work with integer types. Even if they expect and return an integers as meaning they still work with double as type. So any convertions have to rely on a force cast of a double, which is a signed real type, as int is a signed integer type. Using unsigned integers or even longer long types that span over 8 bytes instead of just 6 like double would have overcomplicated the issue. I think these functions have to be re-engineered by MetaQuotes, to work only with integer types and to abide the received integer types that play the operands, just as div and mod work in Pascal implementations. And as for MathRound() , this must be a real rounding function that returns in the integer type that is to receive the result, or in a generic integer type, if it is used in expressions.

File links:
Combinatorics.mqh
combtest.mq5