Рекурсивный алгоритм поиска комбинаций множества в Java

Question

Я пытался найти несколько примеров того, как найти данный набор (может быть строка или массив целых) всех комбинаций в Java. И я наткнулся на этот фрагмент кода (найден в http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html. Я скопировал здесь только связанные части.):

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

Но я действительно не понимаю, как это работает. Кто-нибудь хочет объяснить?

Answer 1

Создать все комбинации данного набора очень просто.У вас есть N элементов, в каждой из комбинаций элемент присутствует или отсутствует, поэтому у вас есть 2 ^ N комбинаций.Эта рекурсивная функция делает именно это.Он выбирает каждый элемент из этого списка и создает комбинации, которые его содержат, и создает комбинации, которые этого не делают.Примечание: он не выводит пустую комбинацию.

Если это все еще не ясно, создайте короткую тестовую строку (например, 3 символа), запустите отладчик и посмотрите, как это работает.

Answer 2

Java-программы начинаются с основного. Этот принимает аргумент, который должен быть целым числом. Он хранит целое число в N. Если пользователь набрал в java и имя программы с 3, то N будет установлено в 3. Это используется для отделения первых N букв алфавита и размещения их в элементах. (В нашем примере abc). Затем он вызывает comb1 (abc), то есть общедоступный comb1, указанный первым.

Далее comb1 вызывает приватную comb1 с двумя аргументами, пустой строкой и abc.

Теперь рекурсия начинается. 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)