[day 27] given an integer n, print out the full permutation from 1 to n | Full Permutation template

This article has been included in the column 《Java Introduction 100 cases 》

order 、 Column Preface

   This column opens , The purpose is to help everyone better master learning Java, Especially some Java Learners' It is difficult to find systematic algorithm learning materials on the Internet to help you get started with algorithms , At the same time, if you have any questions about the contents of the column, you can add my wechat at the end of the article to give you a one-to-one explanation .
   But the most important thing is to think independently , For all the content of this column , Be able to fully master , Write the code completely by yourself , There must be no problem getting started with the algorithm .
   The learning of algorithm must not be short of summary , Here I recommend that you can go to University algorithm community Punch in the learned knowledge , To consolidate and review .
   The only way to learn algorithms well must be Topic sea strategy , Only by accumulating a lot of practice can you practice your skills . Any topic of the column I will start with 【 Title Description 】【 Their thinking 】【 Template code 】【 Code parsing 】 Wait for four plates to explain .

order 、 Preface of this chapter

   The frequency of full array investigation is still a little high ,java Library functions are not included , So you need to write all the permutation functions by yourself , There are many different versions of Full Permutation functions , Here we mainly give two versions of functions that consider order and do not consider order . stay $n$ In small cases , We can also use $n$ Of for Loop to enumerate .

One 、【 Example 1】

1、 Title Description

   Given an integer $n(1\le n\le 9)$, Please print out $[1,n]$ The whole arrangement , There is no need to consider the order .

2、 Their thinking

• $(1)$ Two kinds of fully arranged templates are given , Just shine on your back .

3、 Template code

No dictionary order output template is required

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){
    
            // Realization check Logic 
            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;
    }
}

Output templates in dictionary order

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、 Code parsing

• $(1)$ The first kind of unordered templates is what we often use , Through the recursive exchange of two positions to achieve the enumeration of the full arrangement .dfs Variable k It means that the subscript is determined to be k Number of numbers , When k==n We have found a situation , At this time, you can write according to the requirements of the topic check function , Here we just need to print .
• $(2)$ The first template usually helps us enumerate the answers , Find an arrangement that meets the requirements , Especially the Blue Bridge Cup in previous years , For details, please refer to my blue bridge article .
• $(3)$ Templates output in dictionary order are rarely used , The general topic survey is just for you to print .

3、 ... and 、 Recommendation column

《 Zero fundamental algorithm 100 God 》

Four 、 After-school exercises

Serial number	Topic link	Difficulty rating
1	Book arrangement	2

There are questions about learning ？