生成長度爲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。讓我知道你是否需要任何澄清。

Answer 2

這非常適用也爲空字符串或正== 0

的heavylifting處於第二過載combination()方法（即需要四個參數）。第一個重載簡單地說，輸入字符串轉換成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); 
    }