在一个范围内生成所有可能的字符串

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