Java-求数的全排列dfs
目录
Java 求数的全排列(dfs)
如何求n个元素的全排列，如1 2 3的全排列为 1 2 3 ； 1 3 2 ； 2 1 3； 2 3 1； 3 1 2 ； 3 2 1；
使用的是 递归 ，暴力搜索所有可行的方案。可以用一个一维数组存储每次找到的一种方案。
一、求1~n的全排列
代码示例
// 输出一个n，输出1~n的全排列
import java.util.*;
public class Main{
static int N = 10;
static int n ;
static int path[] = new int[N]; //存储一种可行的方案
static boolean st[] = new boolean[N]; //判断是否被用过 true为被用过 flase为没有
static void dfs(int u){
if(u == n){ // 从第u = 0个位置开始找，当u == n 时一种方案找到完毕输出
for(int i = 0;i<n;i++){
System.out.print(path[i]+" " );
}
System.out.println();
return ;
}
for(int i = 1;i<=n;i++){
if( !st[i] ){
path[u] = i; //在第u个位置存入i
st[i] = true; // 在第u个位置 把i用掉了
dfs(u+1); //寻找第u+1个位置
st[i] = false ; //一种方案寻找完毕，恢复现场
}
}
}
public static void main(String[]args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(0);
}
}运行效果
上述求1~n的全排列，可以扩展为求一个数组的全排列
二、求n个元素的全排列
只需要将上述的dfs方法内的 path[u] = i; 改成输入的元素就行path[u] = nums[i];
代码示例
求输入的n个数的全排列
import java.util.*;
public class Main{
static int N = 10;
static int n ;
static int path[] = new int[N]; //存储一种可行的方案
static boolean st[] = new boolean[N]; //判断是否被用过 true为被用过 flase为没有
static int nums[] = new int[N]; //用来存储输入的n个元素
static void dfs(int u){
if(u == n){ // 从第u = 0个位置开始找，当u == n 时一种方案找到完毕输出
for(int i = 0;i<n;i++){
System.out.print(path[i]+" " );
}
System.out.println();
return ;
}
for(int i = 0;i<n;i++){
if( !st[i] ){
path[u] = nums[i] ; //在第u个位置存入i
st[i] = true; // 在第u个位置 把i用掉了
dfs(u+1); //寻找第u+1个位置
st[i] = false ; //一种方案寻找完毕，恢复现场
}
}
}
public static void main(String[]args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0 ;i<n;i++){
nums[i] = sc.nextInt();
}
Arrays.sort(nums,0,n); //按从大到小输出所有方案，将n个数排序
dfs(0);
}
}运行效果
