快捷導(dǎo)航

Java實(shí)現(xiàn)全排列的三種算法詳解

更新時(shí)間：2022年06月20日 16:57:14 作者：weixin_42320633

從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。本文總結(jié)了Java實(shí)現(xiàn)全排列的三種算法，需要的可以參考下

算法一

基于遞歸與回溯實(shí)現(xiàn)。在排列1，2，3的時(shí)候，先由3向上回溯到2發(fā)現(xiàn)沒有其他可能的情況，再回溯到1，排列為1，3，2再向上回溯到存在其他情況時(shí)，即根節(jié)點(diǎn)然后再排列以2為第一位的情況，重復(fù)上述過程將所有可能結(jié)果全部放入res中。

代碼：

import java.util.ArrayList;
import java.util.List;
 
public class h618_1 {
 
    static List<List<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
        int[] arr = {1,2,3};
 
        h618_1 h1 = new h618_1();
        h1.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;
    }
 
}

算法二

通過交換位置實(shí)現(xiàn)全排列：假設(shè)集合為{1，2，3，4}；

循環(huán)交換位置：1和1交換；1和2交換；1和3交換；1和4交換；

每一次交換再通過遞歸調(diào)用更小的集合：

如：第一次1和1交換確定了1在第一位所以可以看成 {1} + 遞歸交換{2,3,4};

第一次1和2交換確定了2在第一位所以可以看成 {2} + 遞歸交換{1,3,4};

第一次1和3交換確定了3在第一位所以可以看成 {3} + 遞歸交換{1,2,4};

第一次1和4交換確定了4在第一位所以可以看成 {4} + 遞歸交換{1,2,3};

依次類推。

代碼：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class h618_2 {
    static List<List<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
 
        int[] arr = {1,2,3};
        h618_2 h2 = new h618_2();
        h2.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;
 
    }
}

算法三

可以通過添加元素來實(shí)現(xiàn)全排列：

首先定義一個(gè)list 放入第一個(gè)元素為; 然后將剩余的元素依次插入之前的集合元素的所有可能的位置生成新的list；

例如：對(duì){1,2,3,4}實(shí)現(xiàn)全排列

首先定義一個(gè)list 加入第一個(gè)元素為 {1}; 然后第二個(gè)元素2可以插入{1} 的前后兩個(gè)位置形成新list :{21，12 }, 第三個(gè)元素3分別插入list 的元素的所有位置為：{321，231，213，312，132，123}; 以此類推。

代碼：

import java.util.ArrayList;
 
public class h618_3 {
 
    public static void main(String[] args) {
        String aa = "123";
        h618_3 h3 = new h618_3();
        ArrayList<String> res = new ArrayList<>();
        res = h3.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) + "");//初始化,包含第一個(gè)字符
 
        for (int i = 1; i < n; i++) {//第二個(gè)字符插入到前面生成集合的每個(gè)元素里面
            ArrayList<String> res_new = new ArrayList<>();
            char c = A.charAt(i);//新字符
            for (String str : res) {//訪問上一趟集合中的每個(gè)字符串
                //  插入到每個(gè)位置,形成一個(gè)新串
                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;
    }
}

到此這篇關(guān)于Java實(shí)現(xiàn)全排列的三種算法詳解的文章就介紹到這了,更多相關(guān)Java全排列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: