在一個範圍內生成所有可能的字符串

Question

我需要在特定範圍內生成所有可能的字符串。 例如
上界 - aaa
羅威在一起 - ccc

也有可能的情況下aab-caa，hhu - kkk，但不aaz - ccc 值應該是

aaa 
    aab 
    aac 
    aba 
    abb 
    abc 
    aca 
    acb 
    acc 
    caa 
    cab 
    cac 
    cca 
    ccb 
    ccc 

我寫了這樣的方法，但它不工作正確地說，我不知道如何正確地做到這一點，現在我很難找到所有可能的情況，請幫助

public static List<String> generateAllPossibleStrings(String start, String end) { 
     if (start.length() != end.length()) { 
      return null; 
     } 
     List<String> variants = new ArrayList<>(); 
     char startArray[] = start.toCharArray(); 
     char endArray[] = end.toCharArray(); 
     char currentArray[] = Arrays.copyOf(startArray, startArray.length); 
     variants.add(new String(currentArray)); 
     for (int i = startArray.length - 1; i >= 0; i--) { 
      while (currentArray[i] != endArray[i]) { 
       currentArray[i]++; 
       variants.add(new String(currentArray)); 
       for (int j = startArray.length - 1; j > i; j--) { 
        while (currentArray[j] != endArray[j]) { 
         currentArray[j]++; 
         variants.add(new String(currentArray)); 
        } 
        currentArray[j] = startArray[j]; 

       } 
      } 
      currentArray[i] = startArray[i]; 
     } 

     System.out.println(Arrays.toString(variants.toArray())); 
     return variants; 
    } 

對於上面的例子中我得到了

[aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bca, caa, cab, cac, cba, cca] 

正如你可以看到一些值丟失。

請幫助糾正此方法並使其正確工作，或者它應該作爲遞歸方法實施。

說明

爲什麼aaz - ccc是不可能的，因爲在下界任何字符（ccc）應磨碎器，在本例z上限（aaz）對應的字符是磨碎器比c所以這是不正確。

Answer 1

編輯：我可能誤解了這個問題，我認爲結束字符串位於每個位置的起始字符串之上，但它似乎並不是您的其他示例的情況。你能證明你應該在hhu-kkk上輸出什麼，並解釋aaz-ccc有什麼問題嗎？編輯2：正如我懷疑，hhu-kkk也是一個不正確的輸入（u> k），你應該再次編輯你的問題。

將字符串視爲一個數字，您將增加。

當您在一個位置上方結束字符串之上時，請將起始字符串的字母代替並遞增下一個字母，就像帶進位的加法一樣。

這是您的代碼的修改版本。它現在還檢查這兩個字符串是否滿足您描述的所有屬性（如果函數正確使用，則不需要這些屬性）。

public static List<String> generateAllPossibleStrings(String start, String end) { 
    if(start==null||end==null) 
     return null; 
    if (start.length() != end.length()) 
     return null; 
    int n = start.length(); 
    List<String> variants = new ArrayList<>(); 
    char startArray[] = start.toCharArray(); 
    char endArray[] = end.toCharArray(); 
    char currentArray[] = Arrays.copyOf(startArray, startArray.length); 
    variants.add(new String(currentArray)); 

    //We check if the start string is really above the end string as specified 
    //We output an empty string if it is not the case 
    boolean possible = true; 
    for(int i = 0; i<n; i++) 
     possible = possible && (startArray[i]<=endArray[i]); 
    if (!possible) 
     return variants; 


    while(!end.equals(new String(currentArray))){ 
     currentArray[n-1]+=1; 
     int i = n-1; 
     while(currentArray[i]>endArray[i]){ 
      currentArray[i]=startArray[i]; 
      i--; 
      currentArray[i]++; 
     } 
     variants.add(new String(currentArray)); 
    } 

    System.out.println(Arrays.toString(variants.toArray())); 
    return variants; 
} 

Answer 2

我會用single responsibility principle，實施分割到小清的方法和使用遞歸

import java.util.ArrayList; 
import java.util.List; 

public final class Permutations { 

    public static List<String> generate(String begin, String end) { 
     List<String> result = new ArrayList<>(); 

     String current = begin; 
     while (true) { 
      result.add(current); 
      if (current.equals(end)) 
       break; 
      current = getNextPermutation(current, end); 
     } 

     return result; 
    } 

    private static String getNextPermutation(String current, String end) { 
     char[] candidate = current.toCharArray(); 
     createNextPermutation(candidate, current.length()-1, end); 
     return String.valueOf(candidate); 
    } 

    private static void createNextPermutation(char[] candidate, int index, String end) { 
     char c = getNextChar(candidate[index]); 
     if (c > end.charAt(index)) { 
      candidate[index] = 'a'; 
      createNextPermutation(candidate, index-1, end); 
     } 
     else { 
      candidate[index] = c; 
     } 
    } 

    private static char getNextChar(char c) { 
     return (char)(c + 1); 
    } 
}