Рекурсивный итеративный в Java

Question

Я пытаюсь преобразовать этот рекурсивный метод в итеративный метод. Но я застрял посередине.

static void string_recurse(String active,String rest) { 
    if (rest.length() == 0) { 
    System.out.println(active); 
    } else { 
    string_recurse(active + rest.charAt(0), rest.substring(1, rest.length())); 
    string_recurse(active, rest.substring(1, rest.length())); 
    } 
} 

Я не могу понять, как преобразовать этот рекурсивный метод в итеративный. Что делает этот метод, он печатает все слова «подмножества» данного слова. Более формально, если есть строка s_1s_2...s_n он перечисляет все строки s_{i1}s_{i2}...s_{ik} таким образом, что i1, i2, ..., ik является подмножеством {1, ..., n} и i1 < i2 < ... < ik

Например, когда мы называем string_recurse("","abc"); мы получаем вывод:

abc 
ab 
ac 
a 
bc 
b 
c 
(the empty word) 

Answer 1

class Main { 

    static void string_recurse(String active,String rest) { 
     if (rest.length() == 0) { 
      System.out.println(active); 
     } else { 
      string_recurse(active + rest.charAt(0), rest.substring(1, rest.length())); 
      string_recurse(active, rest.substring(1, rest.length())); 
     } 
    } 

    static void string_iterative(String s) { 
     int n = s.length(); 
     for (int mask = (1 << n) - 1; mask >= 0; mask--) { 
      String temp = ""; 
      for (int pos = 0; pos < n; pos++) 
       if (((1 << (n - 1 - pos)) & mask) != 0) 
        temp += s.charAt(pos); 
      System.out.println(temp);    
     } 
    } 

    public static void main(String[] args) { 
     String s = "abcd"; 
     string_recurse("", s); 
     string_iterative(s); 
    } 
} 

Примечание: Если вы знаете, что длина вашей строки никогда не превышает 32, используйте этот итерационный метод. Если вы знаете, что длина строки превышает 32, но ограничивается 64, определите mask как long. Если длина может быть больше, чем 64 stick с оригинальным рекурсивным методом.

Идея этого итерационного метода состоит в том, чтобы сопоставить каждый символ строки либо 1, либо 0. 1 означает, что соответствующий символ принимает участие в текущем подслове, а 0 означает противоположное. Поэтому, чтобы перебрать все «подмножества слов», нам просто нужно зациклиться от 00..0 (n bits) до 11..1(n bits). Это можно сделать только путем циклизации целочисленного диапазона [0, 2^n - 1] и с помощью двоичного представления чисел. Обратите внимание, что в данном примере эти числа зацикливаются обратным образом, чтобы итеративная функция соответствовала рекурсивной.