在Java中查找組合的遞歸算法

我試圖找到一些關於如何在Java中查找給定組（可能是字符串或整數數組）的所有組合的示例。我也碰到這個代碼塊來（在http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html發現我在這裏只複製相關的部分。）：在Java中查找組合的遞歸算法

// print all subsets of the characters in s 
public static void comb1(String s) { comb1("", s); } 

// print all subsets of the remaining elements, with given prefix 
private static void comb1(String prefix, String s) { 
    if (s.length() > 0) { 
     System.out.println(prefix + s.charAt(0)); 
     comb1(prefix + s.charAt(0), s.substring(1)); 
     comb1(prefix,    s.substring(1)); 
    } 
} 

// read in N from command line, and print all subsets among N elements 
public static void main(String[] args) { 
    int N = Integer.parseInt(args[0]); 
    String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; 
    String elements = alphabet.substring(0, N); 

    // using first implementation 
    comb1(elements); 
    System.out.println(); 
}

不過，我真不明白它是如何工作的。有人關心解釋嗎？

來源

2011-08-06 Ahmet Ikras

是不是你有問題的代碼，還是它的基本原則？你可能想要拿一支鉛筆和紙，然後穿過一小塊樣本。從N = 2開始，並遵循代碼用「abc」所做的事情。 – Bart

Java程序從main開始。這一個需要一個參數，它應該是一個整數。它將整數存儲爲N.如果用戶在java中鍵入並且程序名稱爲3，則N將被設置爲3.這用於剝離字母表的前N個字母並將它們放入元素中。（在我們的例子中，abc）。然後它調用comb1（abc），即公共comb1首先列出。

接下來，comb1用兩個參數調用私有comb1，一個空字符串和abc。

現在遞歸開始。專用comb1採用一個前綴和一個字符串（在第一種情況下，一個空字符串和abc）。如果字符串不爲空則：

打印的第一個字符
遞歸調用自己的前綴+的第一個字符作爲新的前綴，其餘爲新的字符串和
遞歸調用自己用與新前綴相同的前綴以及除第一個字符之外的所有字符作爲新字符串。

（這裏是很多人會輕微顫動......盯着它，掛在，是計算機，意義會來。）

(Top level) 
comb1("", "abc") -> *1* a *2* comb1("a", "bc") *3* comb1("", "bc") 

(Second level) 
comb1("a", "bc") -> *1* ab *2* comb1("ab", "c") *3* comb1("a", "c") 
comb1("", "bc") -> *1* b *2* comb1("b", "c") *3* comb1("", "c") 

(Third level) 
comb1("ab", "c") -> *1* abc *2* comb1("abc", "") *3* comb1("ab", "") 
comb1("a", "c") -> *1* ac *2* comb1("a", "") *3* comb1("a", "") 

comb1("b", "c") -> *1* bc *2* comb1("bc", "") *3* comb1("b", "") 
comb1("", "c") -> *1* c *2* comb1("c", "") *3* comb1("", "") 

(Fourth level) 
comb1("ab", "") -> (immediate return, ending recursion) 
comb1("a", "") -> (immediate return, ending recursion) 
comb1("b", "") -> (immediate return, ending recursion) 
comb1("", "") -> (immediate return, ending recursion)

來源

2011-08-06 11:10:32 rajah9

創建給定集合的所有組合非常簡單。你有N個元素，每個元素都有或者沒有，所以你有2^N個組合。這個遞歸函數就是這樣做的。它從該列表中選取每個元素並創建包含它的組合，並創建不包含的組合。注意：它不打印空組合。

如果還不清楚，請創建一個簡短的測試字符串（例如：3個字符），激發一個調試器並查看它是如何工作的。

來源

2011-08-06 10:26:09

在Java中查找組合的遞歸算法

回答

相關問題