| //+------------------------------------------------------------------+
|
| //| 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__
|