考えるとすべての可能な長さの言葉のn

Question

生成：

• 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); 
    } 
} 

Answer 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); 
} 

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

これは空の文字列またはN == 0

heavyliftingが第二過combination()方法（4つのパラメータが取るもの）であるにもうまく機能

Answer 2

。最初のオーバーロードは、単に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); 
    }