[数据结构与算法]算法提高 全排列

输入一个n输出自然数1输出自然数1到n所有不重复的排列，即n的全排列。到n所有不重复的排列，即n的全排列

排列算法参考：https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

import java.util.*;
public class Main {
	public static boolean nextPermutation(int[] array) {
		int i=array.length-1;
		while(i>0&&array[i-1]>=array[i])	i--;//找寻最长不递增序列
		if(i<=0) return false;//已经是最大了
		int j=array.length-1;
		while(array[j]<=array[i-1]) j--;//从最右开始寻找比i-1大的下标为j
		int temp=array[i-1];
		array[i-1]=array[j];
		array[j]=temp;//交换
		j=array.length-1;
		while(i<j) {
			temp=array[i];
			array[i]=array[j];
			array[j]=temp;
			i++;j--;
		}
		//成功完成
		return true;
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] m=new int [n];
		for(int i=0;i<n;i++) {
			m[i]=i+1;
		}
		for(int i=0;i<n;i++)
		System.out.print(m[i]+" ");
		System.out.println();
		for(;nextPermutation(m);) {
			for(int j=0;j<m.length;j++) {
				System.out.print(m[j]+" ");
			}
			System.out.println();
		}
	}
}

dfs搜索算法

import java.util.*;

public class Main {
	static int n;
	static int[] line=new int[10];
	static int[] visit=new int[10]; 
	public static void print() {
		for(int i=1;i<=n;i++) 
			System.out.printf("%d",line[i]);
		System.out.println();
		return ;
	}
	public static void dfs(int step) {//每组第step个数
		if(step>n) {//搜索完了，输出
			print();
		}
		for(int i=1;i<=n;++i) {
			if(visit[i]==1);
			else {
				line[step]=i;//第step个赋值为i
				visit[i]=1;//已经访问
				dfs(step+1);//递归调用
				visit[i]=0;//不使用数值了
			}
		}
		return ;
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		dfs(1);
	}
	
}