-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この反復法を使用してください。文字列の長さは超えているが、 define as32によって制限されていることがわかっている場合。長さがそれ以上になる可能性がある場合は、元の再帰的方法に固執します。64masklong64

この反復メソッドの考え方は、文字列のすべての文字を または のいずれかにマップすること1です0。1は、対応する文字が現在のサブワードに含まれていることを0意味し、その逆を意味します。00..0 (n bits)したがって、すべての「サブセット単語」をループするには、 from toをループするだけです11..1(n bits)。0これは、整数範囲 [ , 2^n - 1] をループし、数値のバイナリ表現を使用するだけで実行できます。与えられた例では、反復関数が再帰関数と一致するように、これらの数値が逆の方法でループされていることに注意してください。

于 2013-10-26T16:53:52.540 に答える