Permutations/Permut_library.mqh

//+------------------------------------------------------------------+
//|                                               Permut_library.mqh |
//|                                        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 "A fast library for combinations and permutations in MQL4."

//  Introduction

//  It doesn't happen very often, but every once in awhile one needs to
//  iterate over all of the combinations or permutations of a set of objects.
//  Or more specifically, given a set of N objects, you want to consider k
//  of them at a time (for each combination or permutation).

//  Practically, combinations and permutations algorithms can be used as a
//  brute-force approach to solve certain problems, by trying every possible
//  combination or permutation, until the optimal solution is found.

//  The cyclic k-permutations algorithm can be used in real world to solve
//  parts of the travelling salesman problem (TSP) or other similar problems
//  like finding the currencies candidate for triangular arbitrage in Forex.

//  Below is a solution to each of these problems and more. The following
//  generic algorithms permit to visit every combination or permutation of
//  a sequence of length N, taken k items at time.

//  Performance Considerations

//  Every effort has been made to make this API library as fast as possible.
//  Many algorithms and libraries for combinations/permutations were reviewed,
//  and lot of benchmarks, code profiling and micro-optimizations were performed.

//  The Heap's algorithm in this library was re-implemented in a more efficient
//  way that provides faster performance than its standard implementation.

#property strict


#ifndef __PERMUTATIONS_H__
#define __PERMUTATIONS_H__


typedef void(*CALLBACK)(int &result[]);
//+------------------------------------------------------------------+
//| Combinations (n choose k)                                        |
//+------------------------------------------------------------------+
/**
 * Combinations are the different ways to choose a k-element subset
 * of an n-set, in which order of selection does not matter.
 *
 * This iterator object allows to iterate all k length lexicographic
 * combinations one by one from an array of n distinct elements.
 *
 * Combinations are emitted in lexicographic (dictionary) sort order
 * of the input.
 *
 * The iterator does not changes the given array.
 *
 * Combinations([A,B,C,D], 3) => ABC ABD ACD BCD
 *
 * count of combinations = nCk
 */
template<typename T>
class CombinationsIterator
  {
private:
   T                 values[];       // 1 2 3 4 5
   int               combIndices[];  // i j k
   int               n,k;

public:
                     CombinationsIterator(const T &arr[],int klen,T &combination[])
     {
      this.k = klen;
      this.n = ArraySize(arr);

      // ArrayCopy(values, arr);
      ArrayResize(values,n);
      for(int i=0; i<n; i++)
        {
         values[i]=arr[i];
        }

      // generate the initial combination indices (0...k-1)
      ArrayResize(combIndices,k);
      for(int i=0; i<k; i++)
        {
         combIndices[i]=i;
        }

      // generate first combination
      ArrayResize(combination,k);
      for(int i=0; i<k; i++)
        {
         combination[i]=values[combIndices[i]];
        }
     }

   // https://stackoverflow.com/a/30225393/4208440
   // https://stackoverflow.com/a/5077264/4208440
   // https://stackoverflow.com/a/44036562/4208440

   // The following code transforms these hard-coded
   // nested for loops to fit any number of indexes
   //	int i, j, k;   //always i < j < k
   //	for (i = 0 ; i < n - 2 ; i++) {
   //		for (j = i + 1 ; j < n - 1 ; j++) {
   //			for (k = j + 1 ; k < n ; k++) {

   // Selects the next combination from the input array and returns true.
   // When there are no more Combinations left, the function returns false.

   bool next(T &combination[])
     {
      // find first index to update
      int indexToUpdate=k-1;

      while(indexToUpdate>=0 && combIndices[indexToUpdate]>=n-k+indexToUpdate)
        {
         indexToUpdate--;
        }

      // no more combinations left
      if(indexToUpdate<0)
         return false;

      // Increment that index, then reset all the following indices to the smallest possible values
      for(int combIndex=combIndices[indexToUpdate]+1; indexToUpdate<k; indexToUpdate++,combIndex++)
        {
         combIndices[indexToUpdate]=combIndex;
        }

      // generate next combination
      for(int i=0; i<k; i++)
        {
         combination[i]=values[combIndices[i]];
        }
      return true;
     }

  };
//+------------------------------------------------------------------+
//| Permutations (all full-length n arrangements)                    |
//+------------------------------------------------------------------+
/**
 * Permutations are the different ordered arrangements of an n-element
 * array. An n-element array has exactly n! full-length permutations.
 *
 * This iterator object allows to iterate all full length permutations
 * one by one of an array of n distinct elements.
 *
 * The iterator changes the given array in-place.
 *
 * Permutations('ABCD') => ABCD  DBAC  ACDB  DCBA
 *                         BACD  BDAC  CADB  CDBA
 *                         CABD  ADBC  DACB  BDCA
 *                         ACBD  DABC  ADCB  DBCA
 *                         BCAD  BADC  CDAB  CBDA
 *                         CBAD  ABDC  DCAB  BCDA
 *
 * count of permutations = n!
 *
 * Heap's algorithm (Single swap per permutation)
 * http://www.quickperm.org/quickperm.php
 * https://stackoverflow.com/a/36634935/4208440
 * https://en.wikipedia.org/wiki/Heap%27s_algorithm
 */

// My fast implementation of Heap's algorithm:

template<typename T>
class PermutationsIterator
  {
   int               b,e,n;

/* control array: mixed radix number in rising factorial base.
   the i-th digit has base i, which means that the digit must be
   strictly less than i. The first digit is always 0, the second
   can be 0 or 1, the third 0, 1 or 2, and so on.
   ArrayResize isn't strictly necessary, int c[32] would suffice
   for most practical purposes. Also, it is much faster */
   int               c[32];

public:
                     PermutationsIterator(T &arr[],int firstIndex,int lastIndex)
     {
      this.b = firstIndex;  // v.begin()
      this.e = lastIndex;   // v.end()
      this.n = e - b + 1;

      ArrayInitialize(c,0);
     }

   // Rearranges the input array into the next permutation and returns true.
   // When there are no more permutations left, the function returns false.

   bool next(T &arr[])
     {
      // find index to update
      int i=1;

      // reset all the previous indices that reached the maximum possible values
      while(c[i]==i)
        {
         c[i]=0;
         ++i;
        }

      // no more permutations left
      if(i==n)
         return false;

      // generate next permutation
      int j = (i & 1) == 1 ? c[i] : 0;    // IF i is odd then j = c[i] otherwise j = 0.
      swap(arr[b + j], arr[b + i]);       // generate a new permutation from previous permutation using a single swap

                                          // Increment that index
      ++c[i];
      return true;
     }

  };
//+------------------------------------------------------------------+
//| k-permutations (n choose k, then all k arrangements)             |
//+------------------------------------------------------------------+
/**
 * Given n distinct objects, list the different ways to place k of
 * them into a row (linear arrangement), in which order matters.
 *
 * The algorithm uses CombinationsIterator to handle the "k out of n"
 * problem. Thus PermutationsIterator has to deal only with all the
 * permutations of "k items" problem.  I.e. For each combination of
 * k out of n items, permute these k items.
 *
 * k_permut([A,B,C,D], 3) => ABC ACB ABD ADB ACD ADC BCD BDC
 *                           BCA CBA BDA DBA CDA DCA CDB DCB
 *                           CAB BAC DAB BAD DAC CAD DBC CBD
 *
 * count of k-permutations = nPk = nCk * k!
 */
void k_permut(int &arr[],int k,CALLBACK callback, bool circular = false)
  {
   if(callback == NULL) return;

// array to receive permutations one by one
   int items[];

// choose "k out of n items"
   CombinationsIterator<int>comboIt(arr,k,items);

   do
     {
      // permute these "k items"
      // to get circular permutations:
      // fix the first item of k, permute next k-1 items.
      PermutationsIterator<int>perm(items,(int)circular,k-1);

      do
        {
         // visit current result
         callback(items);

        }
      while(perm.next(items));

     }
   while(comboIt.next(items));

  }
//+------------------------------------------------------------------+
//| Cyclic k-permutations (n choose k, then all k-ring arrangements  |
//+------------------------------------------------------------------+
/**
 * Given n distinct objects, list the different ways to place k of
 * them into a ring (circular arrangement), in which order matters.
 *
 * Since rotations are considered the same, there are k arrangements
 * which would be the same. Hence, we obtain 1/k distinct arrangements
 * without repeated rotations.
 *
 * A cyclic permutation of K items is done by holding the first item
 * and permuting next k - 1 items.
 *
 * For each unordered combination of "k out of n items":
 * 1) Consider the first item as the starting and ending point.
 * 2) Generate all (k-1)! permutations of remaining items.
 *
 * The algorithm uses CombinationsIterator to handle the "k out of n"
 * problem. Thus PermutationsIterator has to deal only with all the
 * permutations of "k-1 items" problem.  I.e. For each combination of
 * k out of n items, fix the first item of k, permute next k-1 items.
 *
 * ~~rotations allowed~~
 *
 * k_permut([A,B,C,D], 3) =>        ABC ACB ABD ADB ACD ADC BCD BDC
 *                                  BCA CBA BDA DBA CDA DCA CDB DCB
 *                                  CAB BAC DAB BAD DAC CAD DBC CBD
 *
 * ~~distinct arrangements~~ (no rotations)
 *
 * k_permut_cyclic([A,B,C,D], 3) => ABC ACB ABD ADB ACD ADC BCD BDC
 *
 * count of cyclic k-permutations = nPk / k = nCk * (k - 1)!
 */
void k_permut_cyclic(int &arr[],int k,CALLBACK callback)
  {
  k_permut(arr,k,callback,true);
  }
//+------------------------------------------------------------------+
//| count of k-permutations (nPk)                                    |
//+------------------------------------------------------------------+
/**
 * Given n distinct objects, how many ways are there to place k of
 * them into a row (linear arrangement), in which order matters?
 *
 * count of k-permutations, nPk = n! / (n - k)!
 *                          nPk = n(n - 1)(n - 2)...(n - k + 1)
 *
 * different ways to take 3 courses out of 5, in which order matters
 * = 5 * 4 * 3 = 60
 */

// n permute k
long nPk(int n,int k)
  {
// given 1 <= k <= n
   if(k > n) return 0;
   if(k == 0) return 1;

   long result=1;

// if k = n, computes n!
   for(int i=n; i>n-k; --i)
     {
      result*=i;
     }

   return result;
  }
//+------------------------------------------------------------------+
//| count of combinations (nCk)                                      |
//+------------------------------------------------------------------+
/**
 * Given n distinct objects, how many ways are there to select k of
 * them, in which order of selection does not matter?
 *
 * count of combinations, nCk = n! / (n - k)! k!
 *                        nCk = nPk / k!
 *
 * different ways to choose a committee of 3 persons out of 5 candidates
 * = 5 * 4 * 3 / (3 * 2 * 1) = 10
 */

// n choose k
long nCk(int n,int k)
  {
// given 1 <= k <= n
   if(k > n) return 0;
   if(k>n/2) k=n-k; //identity
   if(k == 0) return 1;

   long npk= nPk(n,k);
   long fk = 1;

// compute k!
   for(int i=k; i>0; --i)
     {
      fk*=i;
     }

   return npk / fk;
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * Swaps two variables or two array elements.
 * using references/pointers to speed up swapping.
 */
template<typename T>
void swap(T &var1,T &var2)
  {
   T temp;
   temp = var1;
   var1 = var2;
   var2 = temp;
  }

#endif // #ifndef __PERMUTATIONS_H__