A peek at the ingenious combination of the depth-first search (DFS) algorithm and Java internal classes: solving the full permutation problem

A member inner class is an ordinary class defined inside another class. It can access all members of the outer class (including private members) and can be used by the outer class and other classes. The member inner class implements access to the outer class by holding a reference to the outer class.

2. Usage of internal classes

In the inner class example in the question, we can use the inner class to save the current arrangement and pass it to the next level of recursion. In this way, we can easily access and modify the current arrangement status.

The following is a sample code that demonstrates how to use an inner class to generate an arrangement:

 static class PermutationSolver {
        private int num;
        private int[] nums;
        private boolean[] vis;
        private BufferedWriter bw;

        public PermutationSolver(int num, int[] nums, boolean[] vis, BufferedWriter bw) {
            this.num = num;
            this.nums = nums;
            this.vis = vis;
            this.bw = bw;
        }

        public void solve() throws IOException {
            dfs(0);
        }

        private void dfs(int u) throws IOException {
            if (u == num) {
                for (int i = 0; i < num; i + + ) {
                    bw.write((nums[i] + 1) + " ");
                }
                bw.write("\
");
            } else {
                for (int i = 0; i < num; i + + ) {
                    if (!vis[i]) {
                        vis[i] = true;
                        nums[u] = i;
                        dfs(u + 1);
                        vis[i] = false;
                    }
                }
            }
        }
    }

In the above code example, we have used member inner classes to demonstrate the usage of Java inner classes.

Inner classes are classes nested inside other classes. It has the following characteristics:

1. The inner class can access the private members of the outer class: In the sample code, the PermutationSolver inner class can directly access the private member variable num in the outer class PermutationDemo >, nums, vis and bw.

2. The outer class can access the private members of the inner class: In the example code, the outer class PermutationDemo can create an instance of the PermutationSolver inner class and call methods in it.

3. The inner class can access the method parameters and local variables of the outer class: In the solve method of the sample code, the PermutationSolver inner class can access the dfs method Parameter u.

4. An inner class can have the same variable name as the outer class: In the example code, the inner class’s PermutationSolver class has a variable num with the same name as the outer class, but they represent different meaning.

By using inner classes, we can achieve better encapsulation and organized code structure. Inner classes are usually used to implement auxiliary functions that are closely related to the outer class or to implement an interface.

Supplement:

Introduction to the four types of inner classes:

1. Member Inner Class: A member inner class is nested in an outer class and is closely related to the member variables and methods of the outer class. It can access private members of the outer class and can be directly accessed by the outer class.

2. Static Inner Class: A static inner class is an inner class modified with the static keyword. It has nothing to do with the instance of the external class and can be created and accessed like a normal class without relying on the instance of the external class.

3. Method Local Inner Class: Method Local Inner Class is a class defined inside a method. Its scope is limited to the method in which it is located and can only be accessed within the method. A method inner class can access the parameters and local variables of the outer method, but these variables must be declared final or de facto final.

4. Anonymous Inner Class: An anonymous inner class is an inner class without a specific class name. It is usually used to implement an interface or inherit a class, and only one instance can be created. Anonymous inner classes are generally defined immediately when needed, and can override methods of parent classes or methods that implement interfaces.

The access permissions between inner classes and outer classes are as follows:

1. The outer class can directly access the members of the inner class, even the private members.

2. The inner class can access all members of the outer class, including private members.

3. If the outer class wants to access the members of the inner class, it needs to access it through an instance of the inner class.

The advantages and usage scenarios of internal classes include:

1. Encapsulation: Inner classes can access private members of outer classes, providing better encapsulation.

2. Accessing members of external classes: You can easily access member variables and methods of external classes.

3. Implement multiple inheritance: Inner classes can implement multiple interfaces to achieve multiple inheritance.

4. Code organization and readability: Internal classes can organize related code together to improve code readability and maintainability.

The differences and usage of different types of inner classes are as follows:

1. Member inner classes are often used to describe specific functions of external classes and are closely related to external classes.

2. Static inner classes can be created and accessed independently of outer classes, and are suitable for the definition of classes that meet a specific function.

3. Method inner class is usually used to create an auxiliary class inside a method to implement a specific function.

4. Anonymous inner classes can simplify code, especially when only one instance needs to be created.

The way to create an object of an inner class and access its methods and members is as follows:

1. The instantiation method of member inner class: outer class instance.new inner class (), for example: Outer outer = new Outer(); Outer.Inner inner = outer.new Inner();

2. The instantiation method of static inner class: outer class directly .new inner class(), for example: Outer.Inner inner = new Outer.Inner();

3. The instantiation method of the method inner class: directly use the constructor of the method inner class to create an instance inside the method.

4. Instantiation method of anonymous inner class: Usually, the reference variable of the parent class or interface of the anonymous inner class is used to create an instance.

The relationship and life cycle of internal classes and external classes:

1. There is a strong relationship between the inner class and the outer class, and the inner class can access the members and methods of the outer class.

2. The life cycle of the inner class is bound to the object of the outer class, and instances of the inner class can only be created in instances of the outer class.

4. Question analysis and code implementation

Based on the topic analysis: “Recursive search tree”

Problem-solving ideas: Use the depth-first search algorithm (DFS) to solve the problem. Starting from index 0, continue to enumerate unselected numbers and search downwards recursively. When the subscript u equals n, it means that an arrangement has been completed and the arrangement can be output.

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
    private static int[] path; // selected number
    private static boolean[] st; // tag array
    private static int n; //The number of selected numbers
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        Scanner sca = new Scanner(System.in);
        n = sca.nextInt();
        path = new int[n];
        st = new boolean[n];
        dfs(0); // Start searching from index 0
        bw.flush(); // Refresh the cache area
    }

    private static void dfs(int u) throws IOException {
        if (u == n) { // If n numbers have been selected, output the arrangement
            for (int i = 0; i < n; i + + ) {
                bw.write(path[i] + " ");
            }
            bw.write("\
");
        } else {
            for (int i = 0; i < n; + + i) { // Try to enumerate unselected numbers
                if (!st[i]) {
                    st[i] = true;
                    path[u] = i + 1; // Add the i-th number to the array
                    dfs(u + 1); // Recursive downward search
                    st[i] = false; // Backtrack (undo selection)
                }
            }
        }
    }
}

Combined with java internal classes to achieve:
In this question, we use local inner classes to define a class named Inner in which the DFS function is implemented.

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
    /**
     * How to use inner classes instead of static variables
     */
    public static void main(String[] args) throws IOException {
        Scanner sca = new Scanner(System.in);
        int num = sca.nextInt();
        int[] nums = new int[num];
        boolean[] vis = new boolean[num];
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        class Inner {
            public void dfs(int u) throws IOException {
                if (u == num) { // If num numbers have been selected, output the arrangement
                    for (int i = 0; i < num; i + + ) {
                        bw.write((nums[i]) + " ");
                    }
                    bw.write("\
");
                } else {
                    for (int i = 0; i < num; i + + ) { // Try to enumerate unselected numbers
                        if (!vis[i]) {
                            vis[i] = true;
                            nums[u] = i; // Add the i-th number to the array
                            dfs(u + 1); // Recursive downward search
                            vis[i] = false; // Backtrack (undo selection)
                        }
                    }
                }
            }
        }

        Inner inner = new Inner(); // Create an object of Inner class
        inner.dfs(0); // Call the dfs function
        bw.flush(); // Refresh the cache area
    }
}

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 53164 people are learning the system