Java 求数的全排列(dfs)

时间:2022-02-07作者:klpeng分类:IT综合浏览:698评论:0

 如何求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);
    }
}

运行效果

Java 求数的全排列(dfs)

  上述求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);
    }
}

 运行效果

Java 求数的全排列(dfs)

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢