【第27天】给定一个整数 n ，打印出1到n的全排列 | 全排列模板

本文已收录于专栏《Java入门一百例》

序、专栏前言

   本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法，同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
   但最最主要的还是需要独立思考，对于本专栏的所有内容，能够进行完全掌握，自己完完全全将代码写过一遍，对于算法入门肯定是没有问题的。
   算法的学习肯定不能缺少总结，这里我推荐大家可以到高校算法社区将学过的知识进行打卡，以此来进行巩固以及复习。
  学好算法的唯一途径那一定是题海战略，大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。

序、本章前言

  全排列的考察频率还是有点高的，java并未自带库函数，所以需要自己默写全排列的函数，全排列函数有很多不同版本的，这里我们主要给出考虑顺序和不考虑顺序的两个版本的函数。在$n$不大的情况下，我们也可以使用$n$的for循环进行枚举。

一、【例题1】

1、题目描述

  给定一个整数$n(1\le n\le 9)$，请你打印出$[1,n]$的全排列，不需要考虑顺序。

2、解题思路

• $(1)$给出两种全排列的模板，照着背即可。

3、模板代码

无需字典序输出模板

import java.util.*;

public class Main{
    
    static int[] arr;
    static int n;
    public static void main(String[] args) {
    
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        arr=new int[n];
        for (int i = 0; i <n; i++) {
    
            arr[i]=i+1;
        }
        dfs(0);
    }
    static void dfs(int k){
    
        if (k==n){
    
            //实现check逻辑
            System.out.println(Arrays.toString(arr));
        }
        for (int i = k; i <n; i++) {
    
            swap(i,k);
            dfs(k+1);
            swap(i,k);
        }
    }
    static void swap(int a,int b){
    
        int c=arr[a];
        arr[a]=arr[b];
        arr[b]=c;
    }
}

按字典序输出模板

import java.util.*;

public class Main{
    
    static List<List<Integer>> list=new ArrayList<>();
    public static void main(String[] args)throws Exception{
    
        List<Integer> path=new ArrayList<>();
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        dfs(n,path);
        for(int j=0;j<list.size();j++){
    
            for(int i=0;i<list.get(j).size();i++){
    
                System.out.print(list.get(j).get(i)+" ");
            }
            System.out.println();
        }
    }
    public static void dfs(int n,List<Integer> path){
    
        if(path.size()==n){
    
            list.add(new ArrayList(path));
            return;
        }
        for(int i=1;i<=n;i++){
    
            if(path.contains(i)){
    
                continue;
            }
            path.add(i);
            dfs(n,path);
            path.remove(path.size()-1);
        }
    }
}

4、代码解析

• $(1)$第一种无序模板是我们常使用的，通过递归两两交换位置实现全排列的枚举。dfs变量k代表的是确定下标为k的数，当k==n时说明我们已经找到了一种情况，这时候可以根据题目要求来写check函数，这里我们只需要打印即可。
• $(2)$第一种模板通常能帮助我们去暴力枚举答案，找到某一种排列符合要求，尤其是往年的蓝桥杯尤其爱考，具体可在我的蓝桥真题文章中查看。
• $(3)$按字典序输出的模板比较少用，一般题目考察也只是仅仅让你进行打印。

三、推荐专栏

《零基础学算法100天》

四、课后习题

序号	题目链接	难度评级
1	图书排列	2

学习有疑问？