Full Permutation (DFS and next_permutation solution)

from n Any of the different elements m (m≤n) Elements , Put them in a certain order , It's called from n Take out... Of the different elements m An arrangement of elements . When m=n All permutations are called full permutations .

Today's topic is very simple, that is to give you an integer n , Calculation [1,n] The arrangement and combination of all numbers .
Input format
Enter an integer in the first line n(1≤n≤10).

Output format
The first row outputs the total number of schemes in a full permutation m.

Next, output these in dictionary order m Permutation .

The comparison method of arranged dictionaries is the same as that of strings , For example, two permutations a,b, Start with the first number , The position where the first different number is found is i, Then compare a[i] and b[i] Size , If a[i] Small , that a The dictionary order is small , otherwise b The dictionary order is smaller .

The sample input 1

2

Sample output 1

2
12
21

The sample input 2

3

Sample output 2

6
123
132
213
231
312
321

solution 1： Direct use stl Inside next_permutation(a,a+n)

#include<bits/stdc++.h>
using namespace std;
int n,a[20];
int main(){
    
    cin>>n;
    for(int i=0;i<n;i++){
    
        a[i]=i+1;
    }
    int cnt=0;
    do{
    
        cnt++;
    }while(next_permutation(a,a+n));
    cout<<cnt<<endl;
    do{
    
        for(int i=0;i<n;i++){
    
            cout<<a[i];
        }
        cout<<endl;
    }while(next_permutation(a,a+n));
    return 0;
}

solution 2： DFS
Simple DFS subject , Just search directly .
Each time from 1 - n1−n Choose a number that has not been used before , Mark the previously used numbers . At the end of use, release the previously marked number .
At this time, you will find that the output answer is exactly in dictionary order . In fact, it is also expected , Because every time we try, we start from the smallest .
Note that repeated pruning cannot be added here , Because this is an arrangement , Related to the search order .

#include<bits/stdc++.h>
using namespace std;
bool vis[20];
int n,m=1;
void dfs(int x,int y){
    
    if(x==n){
    
        printf("%d\n",y);
        return;
    }
    for(int i=1;i<=n;i++){
    
        if(!vis[i]){
    
            vis[i]=true;
            dfs(x+1,y*10+i);
            vis[i]=false;
        }
    }
}
int main(){
    
    cin>>n;
    for(int i=1;i<=n;i++){
    
        m*=i;
    }
    printf("%d\n",m);
    dfs(0,0);  
}