“This is the 22nd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

I. Problem description

Output all non-repeating permutations of the natural numbers 1 to n in lexicographical order, that is, the full permutation of n (1≤n≤9), requiring that no repeating digits are allowed in any resulting sequence of digits.

For example, the full permutation of 3 is

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1
Copy the code

Two, the title requirements

Input format

An integer n.

The output format

Each line contains a sequence of digits from 1 to N that are not repeated.

Keep 5 widths for each number.

Third, problem analysis

1. The formula method

See a problem, it is natural to think of C++ inside the full permutation formula, one step to solve. Algorithm, where a represents the name of the array and n represents the size of the array

do
{

}while(next_permutation(a,a+n));
Copy the code

2.DFS

The second method, deep search (DFS), is widely used for some large problems. Although it is more appropriate to use the full permutation formula directly in this problem, today we will look at the use of DFS.

DFS is simply a rat going through a maze, finding a path that doesn’t work, and retracing back.

Breadth search (BFS), by contrast, is more like a maze of rats running from one point in multiple directions until they find an exit.

Take the full array as an example, set an access array visited[10] to judge whether the current number has been visited. 0 represents no, and 1 represents yes. The unvisited numbers are stored in the array and set to 1. The next number is searched in depth until it is greater than a given n. The number in the array is output, backtracking, and so on

Four, coding implementation

1. The formula method

#include<iostream>
#include<algorithm>/ / header files
using namespace std;
int main(a)
{
	int i,n,a[9];/ / initialization
	cin>>n;/ / input n
	for(i=0; i<n; i++) a[i]=i+1;// Initialize the array
	do
	{
		for(i=0; i<n; i++)/ / loop
		{
			printf("%5d",a[i]);// Outputs an array element
		}
		cout<<"\n";
		
	}while(next_permutation(a,a+n));// Complete the list
	return 0;
}
Copy the code

2.DFS

#include<iostream>
using namespace std;
int n,a[10],visited[10] = {0};// Initializes the number array and access array
void DFS(int k)
{
	int i,j;
	if(k>n)/ / is greater than n
	{
		for(j=1; j<=n; j++)// Outputs the elements in the array
		{
			printf("%5d",a[j]);
		}
		cout<<"\n";
	}
	else
	{
		for(i=1; i<=n; i++)// loop judgment
		{
			if(! visited[i])// Whether it has been accessed
			{
				visited[i]=1;/ / set to 1
				a[k]=i;// Assign the current I to k
				DFS(k+1);/ / the next step
				visited[i]=0;/ / back}}}}int main(a)
{
	
	cin>>n;/ / input n
	DFS(1);// Start with 1
	return 0;
}

Copy the code

5. Output results

Enter 3