Non recursive implementation of full permutation algorithm and recursive implementation method of of C++

  • 2020-04-01 23:43:17
  • OfStack

(I) non-recursive all-permutation algorithm
The basic idea is:
      1. Find the smallest of all permutations, P.
      2. Find the permutation Q that is just as big as P is smaller than the others,
      3. Loop through the second step until a maximum permutation is found and the algorithm ends.
The following is described mathematically:
Given the given sequence P =   A1A2A3An (Ai! = Aj, (1) < = I < = n   1, < = j < = n, I! = j   ))
Find a minimum arrangement of P Pmin = P1P2P3Pn   There are   Pi, > P (I - 1) (1) < i. < = n)
Starting with the Pmin, always get the largest order as the input, get the next order.
The method is:
1. From low to high (from back to front), look for "out of trend" Numbers. Find a Pi, make Pi < P (I + 1).
  If we cannot find such a PI, we have found the last full permutation and can return.
2. In P(I +1)P(I +2)Pn, find a Pj, so that Pj is "just bigger than "Pi.
  (" just right greater than "means: the smallest element in the set of all elements greater than Pi in P(I +1)P(I +2)Pn.)
Note: the values of I and j are not changed here, but Pi and Pj are changed.
4. After the exchange, P1P2P3Pn   It's not exactly the last one. Because based on the search in step 1, we have P of I plus 1. > P (I + 2) > . > The Pn
  So even if you swap Pi and Pj, this is still the largest permutation of this part. Inverting the order (to the smallest order) is the next order.
5. Repeat steps 1-4 until no "out of trend" Numbers are found in step 1.

//Swap the values of the two elements in the array a whose subscripts are I and j
void swap(int* a,int i,int j)
{
    a[i]^=a[j];
    a[j]^=a[i];
    a[i]^=a[j];
}

//Invert all elements in array a between index I and index j
void reverse(int a[],int i,int j)
{
    for(;i<j;++i,--j)
    {
         swap(a,i,j);
    }
}

void print(int a[],int length)
{
    for(int i=0;i<length;++i)
         cout<<a[i]<<" ";
    cout<<endl;
}

//Obtain the full array and print the result
void combination(int a[],int length)
{
    if(length<2) return;

    bool end=false;
    while(true)
    {
         print(a,length);

         int i,j;
         //Find the index I of the element that does not conform to the trend
         for(i=length-2;i>=0;--i)
         {
             if(a[i]<a[i+1]) break;
             else if(i==0) return;
         }

         for(j=length-1;j>i;--j)
         {
             if(a[j]>a[i]) break;
         }

         swap(a,i,j);
         reverse(a,i+1,length-1);
    }
}

(2) recursive algorithm
Let E= {e1... , en} represents a set of n elements, and our goal is to generate all the permutations of the set. Let Ei be the set obtained after removing element I from E, perm (X) represents the arrangement of elements in set X, and Ei. P E rm (X) represents the arrangement obtained after adding Ei to each arrangement in perm (X). For example, if E= {a, b, c}, then E1= {b, c}, perm (E1) = (b, c, c b), e1.perm (E1) = (a, b, c, a, c, b). For the basic part of the recursion, n = 1 is used. When there is only one element, there is only one possible arrangement, so perm (E) = (E), where E is the only element in E. When n > When 1, perm (E) = e1.perm (e1) + e2.p E rm (e2) +e3.perm (e3) + ⋯ Plus en. Perm of en. This recursive definition takes n perm (X) to define perm (E), where each X contains n- 1 elements. At this point, the basic and recursive parts required for a complete recursive definition are complete.
When n= 3 and E= (a, b, c), perm (E) =a.perm ({b, c}) +b.perm ({a,c}) +c.perm ({a, b}) can be obtained according to the previous recursive definition. Similarly, according to the recursive definition, perm ({b, c}) =b.perm ({c}) +c.perm ({b, c}), so a.perm ({b, c}) = ab.perm ({c}) + ac.perm ({b}) = ab. c + ac.b = (a b c, ac b). In the same way, b.perm ({a, c}) = ba. Perm ({c}) + bc.perm ({a}) = b. So perm (E) = (a b c, a c b, b a c, b c, b c, b c a,c a,c b a). Note that a.perm ({b, c}) actually contains two permutations: ABC and a c b, with a as their prefix and perm ({b, c}) as their suffix. Similarly, ac.perm ({b}) indicates the arrangement with prefix ac and suffix perm ({b}). Program 1-1 converts the above recursive definition of perm (E) into a C++ function, this code output all prefix l I s t [0: k-1], suffix l I s t [k: m] arrangement. Calling Perm(list, 0, n-1) will get all n factorial of list[0: n-1]. In this call, k=0, m= n-1, so the prefixes of the permutations are empty, and the suffixes are all permutations produced by list[0: n-1]. When k =m, there is only one suffix l I st[m], so list[0: m] is the output to be produced. When k < When m, list[k] is first exchanged with each element in l I st[k: m], then all permutations of list[k+1: m] are generated, and it is used as the suffix of list[0: k]. S w a p is an inline function that is used to exchange the values of two variables

template <class T>
inline void Swap(T& a, T& b)
{
    //Swap a and b
    T temp = a; a = b; b = temp;
}

template<class T>
void Perm(T list[], int k, int m)
{
    //Generate all the permutations of list [k: m]
    int i;
    if (k == m)
    {
         //Output a permutation
         for (i = 0; i <= m; i++)
             cout << list [i];
         cout << endl;
    }
    else //List [k: m] has multiple permutations
    {
         //Recursively produce these permutations
         for (i=k; i <= m; i++)
         {
             Swap (list[k], list[i]);
             Perm (list, k+1, m);
             Swap (list [k], list [i]);
         }
    } 
}


Related articles: