How to implement full permutation in Java algorithm

Algorithm 1

is based on recursion and backtracking. When arranging 1, 2, and 3, first go back from 3 to 2 and find that there are no other possible situations, then go back to 1, arrange 1, 3, 2, and then go back up to when there are other situations, that is, the root node, and then When arranging 2 as the first position, repeat the above process to put all possible results into res.

Code:

import java.util.ArrayList;
import java.util.List;
 
public class h718_1 {
 
    static List<List<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
        int[] arr = {1,2,3};
 
        h718_1 h2 = new h718_1();
        h2.dfs(arr,new ArrayList<>());
        for (List<Integer> re : res) {
            System.out.println(re);
        }
 
    }
 
    public List<List<Integer>> dfs( int[] arr,List<Integer> list){
        List<Integer> temp = new ArrayList<>(list);
        if (arr.length == list.size()){
            res.add(temp);
        }
        for (int i=0;i<arr.length;i++){
            if (temp.contains(arr[i])){
                continue;
            }
            temp.add(arr[i]);
            dfs(arr,temp);
            temp.remove(temp.size()-1);
        }
        return res;
    }
 
}

Algorithm 2

Realize full arrangement by exchanging positions: Assume that the set is {1, 2, 3, 4 };

Loop exchange positions: 1 and 1 exchange; 1 and 2 exchange; 1 and 3 exchange; 1 and 4 exchange;

Each exchange calls a smaller set recursively:

For example: the first exchange of 1 and 1 determines that 1 is in the first place, so it can be regarded as {1} recursive exchange {2,3,4};

The first exchange of 1 and 1 The exchange of 2 determines that 2 is in the first place, so it can be regarded as {2}. The recursive exchange {1,3,4};

The first exchange of 1 and 3 determines that 3 is in the first place, so it can be regarded as {3} Recursive exchange {1,2,4};

The first exchange of 1 and 4 determines that 4 is in the first place, so it can be regarded as {4} Recursive exchange {1,2,3};

And so on.

Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class h718_2 {
    static List<List<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
 
        int[] arr = {1,2,3};
        h718_2 h3 = new h718_2();
        h3.pailie_swap(0,arr);
 
    }
    public void pailie_swap(int index, int[] arr){
        if (arr.length==index){
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = index;i<arr.length;i++){
            swap(i,index,arr);
            pailie_swap(index+1,arr);
            swap(i,index,arr);
        }
 
    }
 
    public void swap(int i,int j ,int[] arr){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
 
    }
}

Algorithm 3

You can achieve full arrangement by adding elements:

First define a list and put the first element into; Then insert the remaining elements into all possible positions of the previous set elements to generate a new list;

For example: implement full arrangement of {1,2,3,4}

First define The first element added to a list is {1}; then the second element 2 can be inserted into the two positions before and after {1} to form a new list: {21, 12}, and the third element 3 is inserted into all the elements of the list respectively. The positions are: {321, 231, 213, 312, 132, 123}; and so on.

Code:

import java.util.ArrayList;
 
public class h718_3 {
 
    public static void main(String[] args) {
        String aa = "123";
        h718_3 h4 = new h718_3();
        ArrayList<String> res = new ArrayList<>();
        res = h4.getPermutation0(aa);
 
        for (String re : res) {
            System.out.println(re);
        }
 
    }
 
    public ArrayList<String> getPermutation0(String A) {
        int n = A.length();
        ArrayList<String> res = new ArrayList<>();
        res.add(A.charAt(0) + "");//初始化,包含第一个字符
 
        for (int i = 1; i < n; i++) {//第二个字符插入到前面生成集合的每个元素里面
            ArrayList<String> res_new = new ArrayList<>();
            char c = A.charAt(i);//新字符
            for (String str : res) {//访问上一趟集合中的每个字符串
                //  插入到每个位置,形成一个新串
                String newStr = c + str;//加在前面
                res_new.add(newStr);
                newStr = str + c;//加在后面
                res_new.add(newStr);
                //加在中间
                for (int j = 1; j < str.length(); j++) {
                    newStr = str.substring(0, j) + c + str.substring(j);
                    res_new.add(newStr);
                }
            }
            res = res_new;//更新
 
        }
        return res;
    }
}

The above is the detailed content of How to implement full permutation in Java algorithm. For more information, please follow other related articles on the PHP Chinese website!