5

与えられた:

  • 文字列の一部の文字input。
  • 整数N

正確に N の長さを持つすべての可能な単語を生成するにはどうすればよいですか?

input = {"a", "b", "a"}とがある場合N=2、出力は次のようになります: ab,aa,ba(重複なし)

私はこれを検索しましたが、得られたのは実装ではなく理解できなかったアルゴリズムだけです。再帰的な方法を実装する必要があることは理解していますが、停止条件の後の時点で立ち往生しています。

public void generate(String input, int length) {        
    if(length == 0) {
        System.out.println(input);
        return;
    }
    //Not sure about this part
    String[] a = input.split("");
    for(int i =0; i<a.length; i++) {
        loop(input+a[i], length-1);
    }
}
4

2 に答える 2

1

これはトリックを行い、任意のinputおよびで動作するはずですN。N = 0またはの動作が明確に定義されていないN > input.length() 

public static void generate(String input, int N) {
    generate("", input, new HashSet<String>(), N);
}

private static void generate(String str, String input, Set<String> dup, int N) {
    if (str.length() == N && dup.add(str))
        System.out.println(str);
    else
        //remove a char form input and add it to str
        for (int i = 0; i < input.length(); i++)
            generate(
                str + input.charAt(i), 
                input.substring(0, i) + input.substring(i + 1), 
                dup, N);
}

これは、より一般的な「すべての順列を計算する」問題から適応されています。一般的な問題では、重複チェックはなくstr、input.isEmpty(). 説明が必要な場合はお知らせください。

于 2013-07-20T07:10:32.737 に答える
0

これは、空の文字列または n == 0 に対してもうまく機能します。

力仕事は、2 番目のオーバーロードcombination()メソッド (4 つのパラメーターを受け取るメソッド) にあります。最初のオーバーロードは、単純に入力文字列を に変換しList<Character>、結果が格納される空のハッシュ セットを準備します。

Set<String> combination(String input, int n) {
  List<Character> letters = new ArrayList<Character>();
  for (int i = 0; i < input.length(); ++i)
    letters.add(input.charAt(i));
  Set<String> results = new HashSet<String>();
  combination("", letters, n, results);
  return results;
}

void combination(String soFar, List<Character> letters, int n, 
    Set<String> results) {
  if (n == 0) { 
    results.add(soFar);
    return;
  }

  int startIndex = soFar.length();
  if (startIndex >= letters.size())
    return;      

  for (int i = startIndex; i < letters.size(); ++i) {
    // ch is the next candidate to add to the result that we're 
    // building (soFar)
    char ch = letters.get(i); 
    // Swap the characters at positions i and position startIndex.
    char temp = letters.get(startIndex);
    letters.set(i, temp);
    letters.set(startIndex, ch);

    // add ch to soFar, compute combinations of length n-1.
    // as startIndex is essentially soFar.length() this means that 
    // the recursive call will only process the remainder of the list.
    combination(soFar + ch, letters, n - 1, result);

    // Swap the characters back - restore the original state.
    letters.set(i, ch);
    letters.set(startIndex, temp);
  }
于 2013-07-20T13:49:52.637 に答える