Java 알고리즘에서 전체 순열을 구현하는 방법

알고리즘 1

은 재귀와 역추적을 기반으로 합니다. 1, 2, 3을 배열할 때에는 먼저 3에서 2로 돌아가서 다른 상황이 없는 것을 확인한 후 다시 1로 돌아가서 1, 3, 2를 배열한 후 다른 상황이 있을 때로 다시 올라간다. , 즉 루트 노드이고, 2를 첫 번째 위치로 배열할 때 위의 과정을 반복하여 가능한 모든 결과를 res에 넣습니다.

코드:

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;
    }
 
}

알고리즘 2

위치 교환을 통해 전체 순열 달성: 집합이 {1, 2, 3, 4}라고 가정합니다.

사이클 위치 교환: 1과 2가 교환됩니다. 1과 3이 교환되고 1과 4가 교환됩니다.

각 교환은 더 작은 세트를 재귀적으로 호출합니다.

예: 1과 1의 첫 번째 교환은 1이 첫 번째 위치에 있다고 결정합니다. {1} + 재귀 교환 {2,3,4}로 간주;

1과 2의 첫 번째 교환은 2가 첫 번째 위치에 있다고 판단하므로 {2} + 재귀 교환 {1,3 ,4};

처음 1 3과의 교환은 3이 우선이라고 판단하므로 {3} + 재귀 교환 {1,2,4};

1의 첫 번째 교환으로 간주할 수 있습니다. 4는 4가 1위라고 판단하므로 {4 } + 재귀 교환 {1,2,3};

등으로 간주할 수 있습니다.

코드:

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;
 
    }
}

알고리즘 3

요소를 추가하여 전체 배열을 달성할 수 있습니다.

먼저 목록을 정의하고 첫 번째 요소를 목록에 넣은 다음 나머지 요소를 이전 세트 요소의 가능한 모든 위치에 순서대로 삽입합니다. 새 목록 생성

예: {1,2,3,4}의 전체 배열 구현

먼저 목록을 정의하고 첫 번째 요소를 {1}로 추가한 다음 두 번째 요소 2를 {1에 삽입할 수 있습니다. } 앞과 뒤의 두 위치는 새 목록({21, 12})을 형성하고 세 번째 요소 3은 목록 요소의 모든 위치({321, 231, 213, 312, 132, 123})에 삽입됩니다. 곧.

코드:

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;
    }
}

위 내용은 Java 알고리즘에서 전체 순열을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!