-4

我正在尝试将此递归方法转换为迭代方法。但是我被困在了中间。

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

1 回答 1

2 
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原来的递归方法。

这种迭代方法的思想是将字符串的每个字符映射到1or 或0。1表示对应字符参与当前子词，0意思相反。因此，要遍历所有“子集词”，我们只需要循环 from 00..0 (n bits)to 11..1(n bits)。这可以通过循环整数范围 [ 0, 2^n - 1] 并使用数字的二进制表示来完成。请注意，在给定的示例中，这些数字以相反的方式循环，以使迭代函数与递归函数一致。

于 2013-10-26T16:53:52.540 回答