This is the fifth day of my participation in the More text Challenge. For details, see more text Challenge

Total permutation problem

Recursive analysis

• An array a[n] is used to store n natural numbers between 1 and N. For I =1 n, after swapping a[1] with a[I] every time, all the n-1 elements in a[2]~a[n] are arranged

Note: we take turns to do the first, → cycle + exchange. After the first one is determined, complete permutation → recursion for the remaining n-1

• Then swap the values of a[1] and a[I] to restore it to the state before this permutation

You have done the first one, please come back to the spot, it’s the next one’s turn to be first.

Once you have the first one, take turns from the remaining n-1 to do the second → loop + swap. Once you have the second one, take turns from the remaining N-2 to do the full permutation. Until there is only one prime, the whole permutation is itself.

inline void perm(int list[], int k, int n)// Find the KTH to NTH permutation of the list array.
{
    int i, t;
    if (k == n)
    {
        for (i = 0; i <= n; i++)
        {
            printf("%d", list[i]);
        }
        printf("\n");
    }

    for (i = k; i <= n; i++)
    {
        swap(list[k], list[i]);
        perm(list, k + 1, n); // Find the total permutations of k+1~n
        swap(list[k], list[i]); }}Copy the code
Dictionary sequence

An important idea of total permutation generation algorithm is to establish A one-to-one mapping relationship between the permutation of elements in set A and some order, and output all permutations of the set in accordance with this order. The order needs to ensure that all permutations can be output, but no permutations can be repeated, or part of the output cycle. A lexicographical order is a way of using this idea to output a complete arrangement. Here, A{1,2,3,4} is used to illustrate the method of using dictionary order to output the full array.

First, lexicographic order is A way of comparing the size of A sequence formed by some arrangement of the set A. Take A{1,2,3,4} for example, the arrangement formed by it is 1234<1243. The comparison method is to compare the corresponding elements of the two sequences from front to back. If the corresponding elements of the current position are the same, the next position will be compared until the first element is different. Above, A1 [1…4]=1234 and A2 [1…4]=1243. For I =1 and I =2, the corresponding elements of the two sequences are equal, but when I =2, A1 [2]=3< A2 [2]=4, so 1234<1243.

The idea of using lexicographic order to output the full permutation is to first output the lexicographic order of the smallest, and then output the lexicographic order of the smallest,…… , and finally output the largest lexicographic order. Here comes the problem of finding the next permutation in the lexicographical order of a given permutation. Here’s the algorithm.

  • For permutation A [1…n], find the maximum value of k that satisfies a[k]
  • In a[k+1…n], find the element L that satisfies the condition such that a[l] obtains the minimum value among all the elements of a[l]>a[k]. That is, a[L]>a[k], but less than all other elements greater than a[k].
  • Exchange a[L] with a[k].
  • For a[k+1…n], reverse the order of the elements in the interval. A [k+1] swaps with a[n], and a[k+2] swaps with a[n-1]… This gives the next permutation of a[1…n] in the lexicographical order.

int arry[3] = { 1.2.2 };//len==3;  
      // Repeats are removed
    void Permutation(a)  
    {  
        int len = 3;  
        int j, k;  
      
        while (true)  
        {  
            printf("%d%d%d\n", arry[0], arry[1], arry[2]);  
      
            for (j = len - 2; j >= 0 && arry[j] >= arry[j + 1]; j--);J >= 0 (j >= 0
      
            if (j < 0) return;/ / end
      
            for (k = len - 1; k > j&&arry[k] <= arry[j]; k--);// Add an equal sign
      
            swap(arry[k], arry[j]);  
      
            for (int l = j + 1, r = len - 1; l < r; l++, r--)  
                swap(arry[l], arry[r]); }}Copy the code
From principle to application

Now that we know how it works, let’s talk about using it,

I don’t know if you remember the two functions next_permutation and prev_permutation in STL’s “algorithm”

  • Next_permutation: For the current permutation, if there is a next permutation in the lexicographical order, return true and assign the next permutation to the current permutation, and if not, put the current permutation in an incremental sort.
  • Prev_permutation: for the current order, if there is a previous order in the dictionary order, return true and assign the previous order to the current order, and if not, place the current order in descending order.
    #include<iostream>  
    #include<algorithm>  
      
    using namespace std;  
      
    int arry[3] = { 1.2.3 };//len==3;  
      
    void Permutation(a)  
    {  
        do  
            printf("%d%d%d\n", arry[0], arry[1], arry[2]);  
        while (next_permutation(arry, arry + 3));  
          
    }  
      
    int main(a)  
    {  
      
        Permutation(a);return 0;  
    }  
Copy the code