組合VS使用遞歸排列

最近我在練習算法問題。我發現了兩個非常相似的問題，並將它們放在一起用於學習目的組合VS使用遞歸排列

問題1：讓所有k個組合從n - 例如N = 4且k = 3，則我們返回{[1,2,3]，[1,3,4]，[2,3,4]，[1,2,4]}

回答：

public static List<List<Integer>> combine(int n, int k) { 
    List<List<Integer>> res = new ArrayList<List<Integer>>(); 
    if(k > n || n <= 0) { 
     return res; 
    } 
    ArrayList<Integer> a = new ArrayList<Integer>(); 
    helper(res, n, k, 1, a); 
    return res; 
} 

private static void helper(List<List<Integer>> res, int n, int k, int start, ArrayList<Integer> a) { 
    if(a.size() == k){ 
     res.add(new ArrayList<Integer>(a)); 
     return; 
    } 

    for(int i=start; i<=n; i++) { 
     a.add(i); 
     helper(res, n, k, i+1, a); 
     a.remove(a.size()-1); 
    } 
}

問題2：有一個陣列的所有排列：{1,2,3} - > {123}，{132}，{213}，{231}，{321}， {312}。

答：

public static List<List<Integer>> permute(int[] num) { 
    List<List<Integer>> rst = new ArrayList<List<Integer>>(); 
    if (num == null || num.length == 0) { 
     return rst; 
    } 

    ArrayList<Integer> list = new ArrayList<Integer>(); 
    helper(rst, list, num); 
    return rst; 
} 

public static void helper(List<List<Integer>> rst, ArrayList<Integer> list, int[] num){ 
    if(list.size() == num.length) { 
     rst.add(new ArrayList<Integer>(list)); 
     return; 
    } 

    for(int i = 0; i<num.length; i++) { 
     if(list.contains(num[i])){ 
      continue; 
     } 
     list.add(num[i]); 
     helper(rst, list, num); 
     list.remove(list.size() - 1); 
    } 
}

對於問題2，我們從指數0開始;對於問題1，爲什麼for循環索引需要在start開始，爲什麼我們需要將start參數傳遞給helper方法？

來源

2015-09-06 catlovespurple

順便說一句，permute（n）= combine（n，n），所以不需要兩個單獨的實現 –

不是，它們是不同的。結合（3,3）會給他的結果只有（1,2,3）.... – catlovespurple

哦，那麼沒關係。 –

查看Prolog代碼時不要感到驚訝。我認爲這將有助於從不同的角度來看問題。

組合是的任意子集包含給定數量的元素的集合。元素的順序是不相關的。

comb(0,_,[]). 
comb(N,[X|T],[X|Comb]):-N>0,N1 is N-1,comb(N1,T,Comb). 
comb(N,[_|T],Comb):-N>0,comb(N,T,Comb).

置換列表大號的是含有列表大號以某種順序的所有元素列表。

perm(List,[H|Perm]):-select(H,List,Rest),perm(Rest,Perm). 
perm([],[]). 

select(X,[X|T],T). 
select(X,[H|T],[H|NT]):-select(X,T,NT).

所以我的答案是：

我們需要組合情況下開始索引指定子集大小。

來源

2015-10-02 07:38:54

組合VS使用遞歸排列

回答

相關問題