遞歸解決一種排列組合的方法

voidking 發布于2019-08-15 15:47 / 1084人閱讀

摘要：解決思路可以將相同屬性的值放到一個中，規定一個的子類，如，將所有的相同屬性值都放到一個中去，此時有多少個屬性就可以得到多少個封裝了相同屬性值的。

問題場景：

比如說一件商品有3中屬性，每個屬性又有3種不同的值，那么此時問，這幾種屬性可能的組合性，相信你很快就得到結果為"333=27"種，此時你可以實現的方式可以為三個for循環嵌套來實現，那么如果場景變了，如果是4種屬性，那你可能就要4個for循環，那么如果此時又變成10個，那是不是要用10個循環了，此時的代碼就顯得笨重并且不易讀，所以此時我們就可以用遞歸實現此業務場景。**

解決思路：

1、可以將相同屬性的值放到一個List中，規定一個List的子類，如ArrayList，將所有的相同屬性值都放到一個ArrayList中去，此時有多少個屬性就可以得到多少個封裝了相同屬性值的ArrayList。
2、將上述生成的所有的ArrayList都放到個List中，即List>;
3、然后將上述List中的ArrayList順序兩個組合成一個新的LinkedList，此處新List子類型是為了和之前的ArrayList區分開來，以便后續區分對待。詳見代碼

代碼示例：

public class MainTest {
    
    private static List returnList = new ArrayList();
    public static void main(String[] args) {

        List> stateLists = new ArrayList>();
        ArrayList als1 = new ArrayList<>();
        als1.add("Color_1");
        als1.add("Color_2");
        ArrayList als2 = new ArrayList<>();
        als2.add("Style_1");
        als2.add("Style_2");
        ArrayList als3 = new ArrayList<>();
        als3.add("Size_1");
        als3.add("Size_2");
        ArrayList als4 = new ArrayList<>();
        als4.add("High_1");
        als4.add("High_2");
        stateLists.add(als1);
        stateLists.add(als2);
        stateLists.add(als3);
        stateLists.add(als4);

        addstatement(stateLists);
        System.out.println("returnList:"+returnList.size()+" "+returnList);
    }

    public static void addstatement(List dataLists){

        int len=dataLists.size();
        //判斷List中的size是否小于2，如果小于說明已經遞歸完成了
        if (len<2){
            returnList=dataLists;
            return;
        }

        //第一個是 ArrayList 或 LinkedList()
        int len0 ;
        if(dataLists.get(0) instanceof  ArrayList){
            len0 = ((ArrayList)dataLists.get(0)).size();
        } else {
            len0 = ((LinkedList)dataLists.get(0)).size();
        }
        int len1 ;
        //第二個一定是 ArrayList
        ArrayList secondList = (ArrayList)dataLists.get(1);
        len1 = ((ArrayList)dataLists.get(1)).size();

        //定義臨時存放排列數據的集合默認的是ArrayList,新組合的是 LinkedList
        LinkedList> tempdataLists=new LinkedList<>();

        //第一層for就是循環dataLists第一個元素的
        for (int i=0;i){
                    ArrayList arr0= (ArrayList) dataLists.get(0);
                    // 創建LinkedList類型與ArrayList區分開來，用于將新的數據重新存儲
                    LinkedList arr=new LinkedList<>();
                    arr.add(arr0.get(i));
                    arr.add(secondList.get(j));
                    //把排列數據加到臨時的集合中
                    tempdataLists.add(arr);
                } else {
                    //到這里就明循環了最少一輪,即數據中只剩下兩個，一個是LinkedList，一個是ArrayList
                    LinkedList> arrtemp= (LinkedList>) dataLists.get(0);
                    LinkedList arr=new LinkedList<>();
                    // 取出老的LinkedList數據賦值給新的LinkedList，同時把第二個ArrayList中的數據賦值給新的LinkedList
                    for (int k=0;k();
        //把還沒排列的數組裝進來，看清楚i=2的喔，因為前面兩個數組已經完事了，不需要再加進來了
        for (int i=2;i
運行結果：
returnList:1 [[[Color_1, Style_1, Size_1, High_1], [Color_1, Style_1, Size_1, High_2], [Color_1, Style_1, Size_2, High_1], [Color_1, Style_1, Size_2, High_2], [Color_1, Style_2, Size_1, High_1], [Color_1, Style_2, Size_1, High_2], [Color_1, Style_2, Size_2, High_1], [Color_1, Style_2, Size_2, High_2], [Color_2, Style_1, Size_1, High_1], [Color_2, Style_1, Size_1, High_2], [Color_2, Style_1, Size_2, High_1], [Color_2, Style_1, Size_2, High_2], [Color_2, Style_2, Size_1, High_1], [Color_2, Style_2, Size_1, High_2], [Color_2, Style_2, Size_2, High_1], [Color_2, Style_2, Size_2, High_2]]]

GPU云服務器云服務器排列組合排列組合算法排列組合算法排列組合java實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69264.html

遞歸小結（一）

摘要：感悟將遞歸當作一種類似的控制結構，通過迭代求解問題，遞歸通過分治求解問題。遞歸解決問題的環節是明確簡單情形明確相同形式的子問題。楊輝三角代碼分析簡單情形，可以理解為遞歸的終止條件，簡單情形里將不遞歸調用或者理解為無法用遞歸解決的情形。感悟將遞歸當作一種類似for/while的控制結構，for/while 通過迭代求解問題，遞歸通過分治求解問題。遞歸是這樣解決問題的。首先，這個問題存...

myeveryheart 2019-08-21 17:16 評論0 收藏0
July 算法習題 - 字符串4（全排列和全組合）

摘要：求字符串的全排列字符串的全排列設計一個算法，輸出一個字符串字符的全排列。的做法沒有結果的，都是在一個字符串上進行的操作。字符串的全組合輸入三個字符，則它們的組合有。因此可以循環字符串長度，然后輸出對應代表的組合即可。求字符串的全排列字符串的全排列設計一個算法，輸出一個字符串字符的全排列。比如，String = abc 輸出是abc,bac,cab,bca,cba,...

tuniutech 2019-08-14 12:11 評論0 收藏0
JS 字符串全排列算法及內存溢出

摘要：問題給定字符串，求出所有由該串內字符組合的全排列。于是我想的辦法是利用尾遞歸優化。算法二尾遞歸終止條件長度為第一次遞歸時，插入首字母遞歸截取了第一個字符的子串函數的第一個參數是本次遞歸的字符串，第二個參數是前個字符的全排列結果。問題給定字符串，求出所有由該串內字符組合的全排列。所包含的字符不重復。輸入：abc 輸出：[abc,acb,bac,bca,cab,cba] 我在實現算法...

sihai 2019-08-22 14:56 評論0 收藏0
前端也需要好好的精進自己的算法

摘要：算法前端發展的再快，也不要忘記精進自己的算法，算法是靈魂和核心。我會把我刷過的算法題總結歸類，不斷完善。算法前端發展的再快，也不要忘記精進自己的算法，算法是靈魂和核心。我會把我刷過的算法題總結歸類，不斷完善。歡迎大家關注。數組和堆棧數組去重旋轉數組如何快速找出兩個數之和等于某一個值的兩個數？快排排序算法大總結快速找到數組中的最大值多維數組的展開二分查找有效的括...

hersion 2019-08-23 10:36 評論0 收藏0
LeetCode 子集合，排列組合，回文分離等問題的通用遞歸算法

摘要：通用算法思路總結初始結果列表?？赡芤獙导判?，方便處理重復元素的情況。書寫遞歸函數，先要考慮原點狀況，一般就是考慮什么情況下要將當前結果添加到結果列表中。每當一個元素添加到當前結果中之后，要再調用遞歸函數，相當于固定了前綴窮舉后面的變化。通用算法思路總結：初始結果列表。可能要將數集排序，方便處理重復元素的情況。調用遞歸函數。書寫遞歸函數，先要考慮原點狀況，一般就是考慮什么...

cfanr 2019-08-14 15:54 評論0 收藏0