자바에서 집합의 조합을 찾는 재귀 알고리즘

Question

자바의 모든 조합을 주어진 집합 (문자열 또는 정수 배열 일 수 있음)을 찾는 방법에 대한 예제를 찾으려고했습니다. 난 정말 어떻게 작동하는지 이해하지 못하고,

// 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(); 
} 

을하지만 (.. 내가 여기에만 관련 부분을 복사 한 http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html에 있음) 그리고 나는이 코드 조각을 건너 온있다. 누구든지 설명해 주겠니?

Answer 1

Java 프로그램은 main에서 시작됩니다. 이 인수는 정수 여야합니다. 사용자가 java로 입력하고 3으로 프로그램 이름을 입력하면 N은 3으로 설정됩니다. 이것은 알파벳의 처음 N자를 떼어내어 요소에 배치하는 데 사용됩니다. (이 예에서는 abc). 그런 다음 comb1 (abc)을 호출합니다. 즉, public comb1이 먼저 나열됩니다.

다음 comb1은 비어있는 문자열 및 abc의 두 인수를 사용하여 개인 comb1을 호출합니다.

이제 재귀가 시작됩니다. private comb1은 접두어와 문자열을 취합니다 (첫 번째 경우 빈 문자열 및 abc). 문자열이 비어 있지 않으면 다음 :

1. 접두사 + 새로운 접두사와 나머지 새로운 문자열로하고
2. 으로 호출 재귀와 마찬가지로 첫 번째 문자로 반복적으로 첫 번째 문자를
3. 전화 자체를 인쇄 새로운 접두사와 같은 접두사와 첫 번째 문자를 제외하고 모두 새로운 문자열로.

(여기서 많은 사람들이 ... 약간 떨게 그것을 응시, 꽉, 컴퓨터, 그리고 의미가 올 것이다 곳입니다.)

(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) 

Answer 2

주어진 세트의 모든 조합을 만드는 것은 정말 간단합니다. 당신은 N 개의 원소를 가지고 있습니다. 각 원소의 원소는 존재하거나 존재하지 않기 때문에 2^N의 조합을가집니다. 그 재귀 함수는 정확하게 그것을합니다. 해당 목록에서 각 요소를 선택하고이를 포함하는 조합을 작성하고 결합하지 않는 조합을 작성합니다. 참고 : 빈 조합은 인쇄되지 않습니다.

아직 명확하지 않은 경우 짧은 테스트 문자열 (예 : 3 자)을 만들고 디버거를 실행하고 작동 방법을 확인하십시오.