Permutation generation algorithm: total permutation of sets

1. Generate an arrangement of 1 ~ n

Ideas

Try to use recursive thinking to solve the problem: first output all the permutations starting with 1 (this step is a recursive call), then output the permutations starting with 2 (also a recursive call), then the permutations starting with 3… and finally the permutations starting with 3.

Mine starting with n.

The characteristics of the arrangement starting with 1: the first one is 1, followed by the arrangement of 2 ~ 9. According to the definition of lexicographic order, these arrangements of 2 ~ 9 must also be arranged in lexicographic order. In other words, it is necessary to “output the permutations 2 ~ 9 in dictionary order”, but it should be noted that when outputting, “1” must be added at the beginning of each permutation. As a result, the designed recursive function requires the following parameters:

The “prefix” sequence that has been determined for output.
A collection of elements that need to be fully arranged so that the first element can be selected in sequence.

pseudocode:

void print_permutation(sequence A, set S)
{<!-- -->
if (S is empty) output sequence A;
else consider each element v of S in order from small to large
{<!-- -->
print_permutation(get a new sequence after adding v at the end of A, S-{<!-- -->v});
}
}

It is not difficult to think of using an array to represent the sequence A, and the set S does not need to be saved at all, because it can be completely determined by the sequence A – the elements that do not appear in A are optional. Functions in the C language cannot determine the number of elements in the array when accepting array parameters, so they need to pass a number of positions that have been filled in, or the current element position that needs to be determined cur.

Code

/********************************************** ***************************
> File Name: Generate an arrangement of 1~n.cpp
> Author: Maureen
> Mail: [email protected]
> Created Time: Friday 10/27 19:21:28 2023
 *************************************************** ************************/

#include <iostream>
using namespace std;

int A[101];

void print_permutation(int n, int *A, int cur) {<!-- -->
    if (cur == n) {<!-- --> //Recursion boundary
        for (int i = 0; i < n; i + + ) {<!-- -->
            printf("%d ", A[i]);
        }
        printf("\\
");
    } else {<!-- -->
        for (int i = 1; i <= n; i + + ) {<!-- --> //Try to fill in various integers i in A[cur]
            bool ok = true; //Check if i has been used
            for (int j = 0; j < cur; j + + ) {<!-- -->
                if (A[j] == i) {<!-- -->
                    ok = false; //If i has already appeared in A[0]~A[cur-1], it cannot be selected again
                }
            }

            if (ok) {<!-- -->
                A[cur] = i;
                print_permutation(n, A, cur + 1); //recursive call
            }
        }
    }
}

int main() {<!-- -->
    int n;
    scanf("%d", & amp;n);
    print_permutation(n, A, 0);
    return 0;
}

2. Resettable full permutation (recursive)

Modify the problem to: input an array P, and output all permutations of each element of the array P in lexicographic order.

Just add P to the parameter list of print_permutation and change if(A[j] == i) to if (A[j] == P[i]), A[cur] = i is modified to A[cur] = P[i]. In this way, just sort all the elements of P from small to large, and then call print_permutation(n, P, A, 0).

The method is good, but there is a small problem: after entering 1 1 1, the program has no output. The reason is that the program prohibits duplication in the A array, and when there are duplicate elements in P, the Array limits are just wrong.

One solution is to count the number of occurrences c1 of P[i] in A[0] ~ A[cur – 1], and the number of occurrences c2 of P[i] in the P array. As long as c1 < c2, it can be called recursively.

else {<!-- -->
for (int i = 0; i < n; i + + ) {<!-- -->
int c1 = 0, c2 = 0;
for (int j = 0; j < cur; j + + ) {<!-- -->
if (A[j] == P[i])
c1 + + ;
}
\t\t
for (int j = 0; j < n; j + + ) {<!-- -->
if (P[j] == P[i]) {<!-- -->
c2++;
}
}
\t\t
if (c1 < c2) {<!-- -->
A[cur] = P[i];
print_permutation(n, P, A, cur + 1);
}
}
}

Enter 1 1 1, and 27 1 1 1 are output. There are no omissions, but there are duplications: first try to use the first 1 as the beginning, after the recursive call is completed, try to use the second 1 as the beginning, after the recursive call is completed, try to use the third 1 as the beginning, and call again recursively . But in fact these three 1’s are the same and should only be recursed once, not three times.

In other words, the enumeration subscript i should take all P[i] values without duplication or omission. Since the P array is already sorted, we only need to check the first element of P and all elements that are not the same as the previous element.

Code

/********************************************** ***************************
> File Name: Resettable full arrangement.cpp
> Author: Maureen
> Mail: [email protected]
> Created Time: Friday 10/27 19:42:25 2023
 *************************************************** ************************/

#include <cstdio>
#include <algorithm>

using namespace std;

int P[101];
int A[101];

// Output the full arrangement of elements in array P. There may be duplicate elements in array P
void print_permutation(int n, int *P, int *A, int cur) {<!-- -->
    if (cur == n) {<!-- -->
        for (int i = 0; i < n; i + + ) {<!-- -->
            printf("%d ", A[i]);
        }
        printf("\\
");
    } else {<!-- -->
        for (int i = 0; i < n; i + + ) {<!-- -->
            if (!i || P[i] != P[i - 1]) {<!-- -->
                int c1 = 0, c2 = 0;
                for (int j = 0; j < cur; j + + ) {<!-- -->
                    if (A[j] == P[i]) c1 + + ;
                }

                for (int j = 0; j < n; j + + ) {<!-- -->
                    if (P[j] == P[i]) c2 + + ;
                }

                if (c1 < c2) {<!-- -->
                    A[cur] = P[i];
                    print_permutation(n, P, A, cur + 1);
                }
            }
        }
    }
}

int main() {<!-- -->

    int n;

    while (scanf("%d", & amp;n) == 1 & amp; & amp; n) {<!-- -->
        for (int i = 0; i < n; i + + ) scanf("%d", & amp;P[i]);
        sort(P, P + n);
        print_permutation(n, P, A, 0);
    }

    return 0;
}

3. Resettable full permutation (next_permutation)

Another way to enumerate all permutations is to start from the lexicographically smallest permutation and keep calling the “find next permutation” process. A library function next_permutation is provided in C++’s STL.

Code

#include<cstdio>
#include<algorithm>
using namespace std;

int main() {<!-- -->
  int n, p[10];
  scanf("%d", & amp;n);
  for(int i = 0; i < n; i + + )
  scanf("%d", & amp;p[i]);
  \t
  sort(p, p + n); // Sort to get the minimum arrangement of p
  
  do {<!-- -->
    for(int i = 0; i < n; i + + )
    printf("%d ", p[i]); // Output arrangement p
    printf("\\
");
  } while(next_permutation(p, p + n)); // Find the next permutation
  
return 0;
}

This code also works for resettable.

4. Summary

There are two common methods of enumeration permutation: one is recursive enumeration, and the other is using next_permutation in STL.